确实不会的多项式

写总结的地方

• 将式子转化为卷积形式: $\displaystyle{\sum_{i=1}^n A_i B_{n-i}}$

P3338 [ZJOI2014]力

• 题意：
  求 $E_j=\displaystyle{\sum_{i=1}^{j-1}\frac{q_j}{\left(i-j\right)^2} - \sum_{i=j+1}^n \frac{q_j}{\left(i-j\right)^2}}$

  $q_i被消掉了qwq$

• 解：

  • 先简化数据范围

    $$\sum_{i=1}^{j-1} \Rightarrow \sum_{i=0}^{j}$$

  • 化成能算的样子

    设 $f[i]=q_j \ , f’[i]=f[n-i] \ , \ g[i]=\frac{1}{i^2}$

    $$\begin{aligned} 原式 &=\underbrace{\sum_{i=1}^j f[i] \cdot g[j-i]}_{\rm 已经是卷积形式} - \sum_{i=j}^n f[i] \cdot g[i-j] \\ &=\sum_{i=1}^j f[i] \cdot g[j-i] - \underbrace{\sum_{i=0}^{n-j} f[i+j] \cdot g[i]}_{\rm 然而还不能算} \\ &设 t=n-j \\ &=\sum_{i=1}^j f[i] \cdot g[j-i] - \sum_{i=0}^t f'[t-i] \cdot g[i] \\ \end{aligned}$$

  $\bf{Trick:}$ 翻转数列

  && 把函数设成数组以看起来更好算

P3723 [AH2017/HNOI2017]礼物

• 题意：

  给定两个序列 $a,b$ ，顺序可以移动，求 $\displaystyle{\sum_{i=1}^n \left(a_i-b_i+c \right)^2}$ 最小值

• 解：

  $$原式=\underbrace{\sum_{i=1}^n a_i^2+\sum_{i=1}^n b_i^2}_{\rm [一]可以预处理} - \underbrace{\sum_{i=1}^n a_ib_i}_{\rm [二]见下面} + \underbrace{nc^2 + 2c\left(\sum_{i=1}^na_i - \sum_{i=1}^nb_i \right)}_{\rm [三]关于 c 的二次函数}$$

  由题：要取 $\displaystyle{\sum_{i=1}^n a_ib_i}$ 的最大值

  考虑移动 $k$ 位时：

  先把环 $b$ 变为链 $\Rightarrow$ $b[i+n]=b[i]$

  转化为考虑 $\displaystyle{\sum_{i=1}^n a_ib_{i+k} }$

  翻转 $a$ 得 $\displaystyle{\sum_{i=1}^n b_{i+k} \cdot a_{n-i+1}}$ ， 符合卷积形式

  $\therefore \tt{FFT}\left(a_{reserved}\right),\tt{FFT}(b)$

  $\bf{Trick:}$ 由于 $c$ 是整数，用二次函数对称轴来算 [式三],比枚举 $-100\leq c \geq 100$ 更好

  算出$\left\lfloor -\frac{a}{b} \right\rfloor$ 和 $\left\lceil -\frac{a}{b} \right\rceil$ ， 取 $\min$

P5488 差分与前缀和

• 题意：

  求数列 $a$ 的 $k$ 维前缀和或差分

• 解：

  设 $\displaystyle{F(x)=\sum_{i=0}^\infty a_ix^i }$

  • 前缀和

    比较前缀和与卷积

    $\displaystyle{a_i=\sum_{j=1}^i a_j \qquad \And\And \qquad S_i=\sum_{j=1}^i A_j B_{i-j}}$

    发现需要卷一个系数都为 $1$ 的多项式 $G(x)$

    以样例为例：

    $$\begin{aligned} &F(x)*G(x) \\ &=(1+9x+2x^2+6x^3+0x^4+8x^6+7x^7) \cdot (1+x+x^2+x^3+x^4+ \cdots +x^{\infty}) \\ &=1+\underbrace{9x^1 + \underbrace{2x^2 + \underbrace{6x^3 + \underbrace{0x^4 + \underbrace{8x^6 + \underbrace{7x^7}_{\rm 系数+8}}_{\rm 系数+0}}_{\rm 系数+6}}_{\rm 系数+2}}_{\rm 系数+9}}_{\rm 系数+1} \end{aligned}$$

发现 $F(x)\cdot G(x)$ 所得多项式就是 $F$ 的一阶前缀和

$\displaystyle{\therefore 显然有 G(x)=\frac{1}{1-x}}$

$\displaystyle{\therefore k阶前缀和 \Rightarrow
 F(x) \cdot \frac{1}{\left(1-x \right)^k}}$

$\displaystyle{\frac{1}{\left(1-x \right)^k} 的第 n 项系数就是 \dbinom{n+k-1}{k-1} }$

$\displaystyle{\therefore a_i=\sum_{j=1}^{i-1}\dbinom{j+k-1}{k-1} \cdot a_{i-j} }$

设组合数递推式 $g_i=\dbinom{i+k-1}{k-1}$

$$\begin{aligned}
\therefore
g_i
&=\frac{g_{i-1}\times (k+i-1)}{i}\%p &\text{只会在计算中用到这个}\\
&=\left(\frac{g_{i-1} }{i}\%p \right)\times ((k+i-1)\%p) \\
&=\left(\frac{g_{i-1} }{i}\%p \right)\times ((k\%p+i-1)\%p) \\ &\text{只是为了推 $k$ 可以取模} \\
\end{aligned}$$

$\therefore$ 可以对 $k$ 取模

• 差分

  易得 $F(x) \times (1-x)$ 所得的多项式就是差分后

  同理得 $\left(1-x\right)^k$

  $$\begin{aligned} B &=F(x) \cdot \left(1-x\right)^k \\ &=F(x) \cdot \sum_{i=0}^{\infty} \dbinom{k}{i} \left(-x \right)^i \\ &=F(x) \cdot \sum_{i=0}^{\infty} \left(-1 \right)^i \cdot \dbinom{k}{i} x^i \\ \end{aligned}$$

  看组合数递推式: $\dbinom{k}{i}$

  $$\dbinom{k}{0}=1$$ $$\dbinom{k}{1}=\frac{k!}{(k-1)!}=k$$ $$\dbinom{k}{2}=\frac{k!}{2!(k-2)!}=\frac{k(k-1)}{2}$$ $$\dbinom{k}{3}=\frac{k!}{3!(k-3)!}=\frac{k(k-1)(k-2)}{2\times 3}$$ $$\dbinom{k}{i}=\dbinom{k}{i-1} \cdot \frac{k-i+1}{i} \qquad\text{用这个递推}$$