[ZJOI2014] 力

首先转化一下式子：

Ek=∑i=1k−1qi(k−i)2−∑i=k+1nqi(k−i)2=E1k+E2kE_k=\sum_{i=1}^{k-1}\frac{q_i}{(k-i)^2}-\sum_{i=k+1}^n \frac{q_i}{(k-i)^2}=E_{1k}+E_{2k}

可以令 q0=0q_0=0，就能推出 E1kE_{1k} 的卷积形式：

E1k=∑i=0k−1qi(k−i)2=∑i=0k−1figk−1−iE_{1k}=\sum_{i=0}^{k-1}\frac{q_i}{(k-i)^2}=\sum_{i=0}^{k-1} f_ig_{k-1-i}

其中 fi=qi,gi=1(i+1)2f_i=q_i,g_i=\cfrac{1}{(i+1)^2}。

由于卷积的指标是从 00 开始的，所以对于 E2kE_{2k}，需要令 j=n−i+1j=n-i+1，那么：

E2k=∑j=1n−kqn−j+1(n−k−j+1)2=∑j=0n−kfjgn−k−jE_{2k}=\sum_{j=1}^{n-k}\frac{q_{n-j+1}}{(n-k-j+1)^2}=\sum_{j=0}^{n-k}f_jg_{n-k-j}

其中 fi=qn−i+1,gi=1(i+1)2f_i=q_{n-i+1},g_i=\cfrac{1}{(i+1)^2}，并且 qn+1=0q_{n+1}=0。

复杂度主要是一次 FFT，为 O(nlog⁡n)O(n\log n)。

AC Code。

[AHOI2017/HNOI2017] 礼物

首先，给 yy 整体 +c+c 对贡献的影响等价于对 xx 整体 −c-c，所以我们可以把这个条件转化成 xx 整体加一个整数。

把这个式子拆一下：

∑i=1n(xi+c−yi)2=nc2+(2∑i=1nxi−2∑i=1nyi)c+∑i=1nxi2+∑i=1nyi2−2∑i=1nxiyi\sum_{i=1}^n(x_i+c-y_i)^2=nc^2+(2\sum_{i=1}^n x_i-2\sum_{i=1}^n y_i)c+\sum_{i=1}^n x_i^2+\sum_{i=1}^ny_i^2-2\sum_{i=1}^n x_iy_i

可以看出，这是一个关于 cc 的二次函数，并且二次项、一次项系数与排列顺序无关。

现在我们要求常数项的最小值，转化为求 ∑xiyi\sum x_iy_i 的最大值。

如果把 y1∼yny_1\sim y_n 复制一遍到 yn+1∼y2ny_{n+1}\sim y_{2n}，会发现每一种排列都对应着 x1∼xnx_1\sim x_n 与 yd∼yn+dy_{d}\sim y_{n+d} 对应相乘再相加。

手玩一下就可以知道如果令 f={0,x1,x2,…,xn,0,0,… }f=\{0,x_1,x_2,\dots,x_n,0,0,\dots\}，g={yn,yn−1,…,y1,yn,yn−1,…,y1}g=\{y_n,y_{n-1},\dots,y_1,y_n,y_{n-1},\dots,y_1\}，然后 h=f∗gh=f*g 那么 hn∼h2n−1h_n\sim h_{2n-1} 就是我们要求的答案了。

复杂度主要是一次 NTT，为 O(nlog⁡n)O(n\log n)。

AC Code。

[CF755G] PolandBall and Many Other Balls

状态转移方程比较简单：fn,k=fn−1,k+fn−1,k−1+fn−2,k−1f_{n,k}=f_{n-1,k}+f_{n-1,k-1}+f_{n-2,k-1}。

如果我们把 fnf_n 看成一个最高 kk 次的多项式，那么就有 fn=fn−1+xfn−1+xfn−2f_n=f_{n-1}+xf_{n-1}+xf_{n-2}。

这可以写成 [fnfn−1]=[x+1x10][fn−1fn−2]\begin{bmatrix}f_n\\f_{n-1}\end{bmatrix}=\begin{bmatrix}x+1&x\\1&0\end{bmatrix}\begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix}。

显然地，f0=1f_0=1，f1=1+xf_1=1+x，这些多项式的次数不超过 kk，所以复杂度是 O(klog⁡klog⁡n)O(k\log k\log n)。

AC Code。

[TJOI2017] DNA

下面设 SS 为短串，TT 为长串。

我们需要对每一个位置求出失配数量，考虑到本题目字符集小，所以逐个考虑所有字符。

设当前字符是 11，非当前字符是 00，那么我们希望 Si=1S_i=1 时 Ti=1T_i=1，Si=0S_i=0 时 TiT_i 无所谓，所以可以写出 ∑Si(1−Ti)\sum S_i(1-T_i) 就是每一段的失配数量。

把每个字符的失配数量加起来就是总的失配数量。

这个和式同样可以把 SS 串翻转过来，并在后面补 00 到与 TT 一样长，那么每一个和就对应它们卷积的一个位置。

复杂度为单次 O(∣Σ∣∣T∣log⁡∣T∣)O(|\Sigma||T|\log |T|)，其中 Σ\Sigma 是字符集。

AC Code。

和上面的题目一样，可以逐个考虑所有字符。

这里的前后 kk 个字符，可以用一个差分数组来把每个字符前后 kk 个位置都打上标记。

复杂度为 O(∣Σ∣nlog⁡n)O(|\Sigma|n\log n)，其中 Σ\Sigma 是字符集。

AC Code。