Muyang的博客

信息里的 FFT 指的是快速（离散）傅里叶变换，用来把一个多项式 $O(n\log n)$ 地用点值法来表示，因此可以用来做多项式乘法。与物理上（连续的）傅里叶变换有所区别（我之前一直以为和物竞里的是一回事）。 引入如果我们有两个 $n$ 次的多项式，我们如何计算这两个多项式相乘呢？首先，朴素地计算是 $O(n^2)$ 的，好慢啊。我们先从单个多项式入手。 多项式的点值表示通过拉格朗日插值法或者方程组，我们知道 $n+1$ 个点能确定一个 $n$ 次多项式（

本篇是一些高级一点的数据结构，好像都是树。。。 线段树合并其实就是动态开点。这个可以理解一下，帮助理解主席树。用两种写的形式，一种是函数里传地址，直接修改，另一种是让函数返回新节点的位置。 123456789101112131415161718192021222324252627int update(int &o,int l,int r,int pos,int x){ if(o==0) o=++idx; if(l==r){ tr[o]+=x; col[o]=pos; return o; } int mid=l+r>>1; if(pos<=mid) update(ls[o],l,mid,pos,x); else update(rs[o],mid+1,r,pos,x); pushup(o); return o;}int merge(int &x,int y,int l,int r){//把y合并到x上，返回的的是...

我们先将题目形式化。$$\begin{cases}a_1+a_2 \equiv b_1 \pmod{m}\a_2+a_3 \equiv b_2 \pmod{m}\\dots\a_{n-1}+a_n \equiv b_{n-1} \pmod{m}\end{cases}$$做完本题的 Easy Version 后，我们发现其实只要确定了最终 $a_1$ 的值，后面的项模 $m$ 的余数都是可以确定的，因此我们考虑枚举最终 $a_1$ 为 $x$，将答案写成 $x$ 的函数。 $$\begin{cases}a_1 \equiv x \pmod{m}\a_2 \equiv b_1-a_1 \equiv b_1-x \pmod{m}\a_3 \equiv b_2-a_2 \equiv b_2-b_1+x \pmod{m}\\dots\a_n \equiv b_{n-1}-a_{n-1} \equiv b_{n-1}-b_{n-2}+b_{n-3}\dots - (-1)^n x\pmod{m}\end{cases}$$ 不难发现，令 $c_i \equiv b_i-b_{i-1}+b_{i...