P3338 [ZJOI2014]力
\[\begin{aligned} E_i&=\sum_{j=1}^{i-1}\frac{q_j}{(i-j)^2}-\sum_{j=i+1}^n\frac{q_j}{(i-j)^2} \end{aligned} \]设 \(f(x)=q_x\)，\(g(x)=x^2\)，\(h(x)=q_{n-x+1}\)。
前半部分为 \((f*g)(i)\)，后半部分为 \((h*g)(i)\)。
P3723 [AH2017/HNOI2017]礼物
\[\begin{aligned} &\sum_{i=0}^{n-1}(x_i+p-y_i)^2\\ &=\sum_{i=0}^{n-1}x_i^2+y_i^2+p^2+2(x_i-y_i)p-2\sum_{i=0}^{n-1}x_iy_i \end{aligned} \]设 \(d\in[0,n-1]\)。
\[\begin{aligned} &\sum_{i=0}^{n-1}x(i)y(i+d)\\ &=\sum_{i=0}^{n-1}x(n-i-1)y(i+d) \end{aligned} \]P5488 差分与前缀和
设 给定的多项式为 \(F(x)\)，那么 \(k\) 维前缀和为
\[F(x)\times \frac{1}{(1-x)^k} \]\(k\) 维差分为
\[F(x)\times (1-x)^k \]考虑差分的情况怎么做
\[(1-x)^k=\sum_{i=0}^{n}(-1)^{i}\binom{k}{i}x^i \]\(\binom{k}{0}=1\)，\(\binom{k}{i}=\binom{k}{i-1}\times\frac{k-i+1}{i}\)。
考虑前缀怎么做，第 \(x\) 项的答案为 \(\binom{x+k-1}{k-1}\)。
P5641 【CSGRound2】开拓者的卓识
考虑 \(y\) 会在 \(sum(k,1,x)\) 中计算几次。
\[\begin{aligned} sum(k,1,x) &=\sum_{y=1}^xa(y)\binom{x-y+k-1}{k-1}\binom{y-1+k-1}{k-1}\\ &=\sum_{y=1}^xf(y)g(x-y) \end{aligned} \]其中，\(f(x)=a(x)\binom{x+k-2}{k-1}\)，\(g(x)=\binom{x+k-1}{k-1}\)。
\(k\) 很大，因此需要递推计算 \(f(x)\) 和 \(g(x)\)。
\[\binom{x+s}{t}=\binom{x+s}{x+s-t} \]CF623E Transforming Sequence
设 \(f(i,j)\) 表示前 \(i\) 个数中选择 \(j\) 个 \(1\) 的方案数（只考虑这 \(j\) 个 \(1\)，忽略其它 \(k-j\) 个位置）。
\[f(i,j)=\sum_{p=1}^jf(i-1,j-p)\binom{j}{p}2^{j-p} \]\[f(n+m,i)=\sum_{j=0}^if(n,j)f(m,i-j)\binom{i}{j}2^{mj} \]于是可以倍增
\[f(2n,i)=\sum_{j=0}^if(n,j)f(n,i-j)\binom{i}{j}2^{nj} \]这就体现了设 \(f(i,j)\) 为只考虑 \(j\) 个 \(1\) 的好处，它使得 dp 值可以合并。
如果不这么设，比如设 \(f(i,j)\) 表示前 \(i\) 个数中选择 \(j\) 个 \(1\) 且要考虑位置的方案数，那么就只能得到一个递推式而得不到合并的式子，就无法解决该问题。
得到了合并的 dp 式，就可以使用倍增 FFT 解决。
CF1251F Red-White Fence
红板个数很少，于是考虑对每个红板单独处理。
先考虑长度小于红板的白板长度不重复的情况。
假设有 \(n\) 个这样的白板，选 \(i\) 个的答案为 \(\binom{n}{i}2^i\)。
现在考虑重复的情况，可以发现，重复个数大于 \(2\) 等价于重复个数为 \(2\)。
假设有 \(m\) 对重复的白板，选 \(i\) 个的答案为 \(\binom{2m}{i}\)。
设选择 \(x\) 个白板的答案为 \(f(x)\)。
\[f(x)=\sum_{i=0}^x\binom{n}{i}2^i\binom{2m}{x-i} \]算出所有 \(f(x)\) 统计一下答案就行了。
标签：begin,end,07,省选,多项式,sum,frac,binom,aligned From： https://www.cnblogs.com/yanchengzhi/p/17002015.html