动态规划 1

多项式 1

多项式 2

普通莫队算法

状压 DP

数位 DP

AtCoder Beginner Contest 174 pro:5/6/6 rk:1676/9750

洛谷p3723

$\text{FFT},\text{NTT}$

给定两个长度为 $n$ 的序列 $a,b$。其中 $b$ 可以循环移动，求 $\min\left(\sum_{i=0}^{n-1}(a_i-b_i+x)^2\right)$，$x$ 为任意整数。

$$\sum_{i=0}^{n-1}(a_i-b_i+x)^2=\sum_{i=0}^{n-1} \left(a_i^2+b_i^2-2a_ib_i+2(a_i-b_i)x+x^2\right)=\sum_{i=0}^{n-1}\left(a_i^2+b_i^2\right)+2x\sum_{i=0}^{n-1}(a_i-b_i)+nx^2-2\sum_{i=0}^{n-1}a_ib_i$$

发现不管 $b$ 如何循环移动，$\sum_{i=0}^{n-1}\left(a_i^2+b_i^2\right)$ 和 $\sum_{i=0}^{n-1}(a_i-b_i)$ 为定值。

于是 $\sum_{i=0}^{n-1}\left(a_i^2+b_i^2\right)+2x\sum_{i=0}^{n-1}(a_i-b_i)+nx^2$ 为系数确定的二次函数，可以直接求最小值，问题转化为求 $\max\left(\sum_{i=0}^{n-1}a_ib_i\right)$。

考虑倍长 $b$ 数组，再反转 $a$ 数组，于是式子转化为

$$\max_{0\le k\lt n}\left(\sum_{i=0}^{n-1}a_{n-1-i}b_{i+k}\right)$$

令 $c_i=\sum_{j=0}^i a_jb_{i-j}$，于是式子转化为

$$\max_{0\le k\lt n} c_{n-1+k}$$

考虑 $\text{FFT}$ 或 $\text{NTT}$ 求解，时间复杂度 $O(n\log n)$。

$\text{FFT}$ 经典题。