「LuoguP3723」「AHOI / HNOI2017」礼物
题意
给定两个长度为\(n\)的正整数序列\(a_0,a_1,a_2,\cdots,a_{n-1}\)和\(b_0,b_1,b_2,\cdots,b_{n-1}\)，满足\(a_i,b_i\le m\)。
求\[\sum_{i=0}^{n-1} ((a_i+c_0)-(b_{(i+k)\bmod n}+c_1))^2\]的最小值，其中\(k,c_0,c_1\)是非负整数。
\(n\le 5\times 10^4,m\le 100\)。
题解
观察上式，可以发现我们并不关心\(c_0,c_1\)具体的值，只关心\(c_0-c_1\)的值。记\(c=c_0-c_1\)，显然有\(-m\le c\le m\)。于是变成了求\[\sum_{i=0}^{n-1} (a_i-b_{(i+k)\bmod n}+c)^2\]的最小值，其中\(0\le k\le n-1,-m\le c\le m\)。
最朴素的做法是直接枚举\(k,c\)计算答案，时间复杂度\(O(n^2m)\)。
这个和的平方的形式很难优化，考虑把它展开：
\[\begin{aligned} &\quad \sum_{i=0}^{n-1}(a_i-b_{(i+k)\bmod n}+c)^2 \\ &=\sum_{i=0}^{n-1}(a_i^2+b_{(i+k)\bmod n}^2+c^2-2a_ib_{(i+k)\bmod n}+2a_ic-2b_{(i+k)\bmod n}c) \\ &=-2\sum a_ib_{(i+k)\bmod n}+\sum a_i^2+\sum b_i^2+2c\sum (a_i-b_i)+nc^2 \end{aligned}\]
然后我们发现，\(k,c\)并没有同时影响答案中的某一项。第一项为与\(k\)有关的式子，显然后面部分为关于\(c\)的一个二次函数。后面部分可以直接用二次函数的顶点公式计算（注意\(c\)是整数，需要讨论两种情况），也可以直接枚举\(c\)进行计算。
如果前面部分也直接枚举\(k\)进行计算的话，时间复杂度为\(\mathcal O(n^2)\)，仍不能通过。
先不考虑系数。\(\bmod\)很难处理，考虑把\(b\)倍长，原式变成了\(\sum a_ib_{i+k}\)。联系卷积的基本形式\(c_i=\sum_{j=0}^{i} a_jb_{i-j}\)，可以发现需要满足\(a,b\)的下标之和为\(c\)的下标，即一个与\(j\)无关的值。那么我们考虑把\(a\)翻转，原式变成了\(\sum a_{n-i-1}b_{i+k}\)，此时\(n-i-1+i+k=n+k-1\)，是一个与\(i\)无关的值。于是就可以FFT了。由于\(0\le k\le n-1\)，所以对应的答案（假设\(c=a*b\)）就是\(c_{n-1},c_{n},c_{n+1},\cdots,c_{2n-2}\)。
啥？FFT精度爆了？因为\(m\le 100\)，所以\(0\le c_i\le nm^2\le 5\times 10^8< 998244353\)，直接用NTT即可。
时间复杂度\(O(n\log n)\)。
代码
评测记录，开O2，总时间170ms，目前在第一页。
1 |
|
