P3723 [AHOI2017/HNOI2017]礼物 题解
题面
又是一道推式子+FFT。看到有些式子看起来很卷，不要犹豫，自信一点，说不定就推出来了呢。
设加的数为 \(x\)，转完之后两个数组每一位对应为 \(a[1...n]\) 和 \(b[1...n]\)，可得：
要求 \(\min\{\sum_{i=1}^{n}(a_i+x-b_i)^2\}\)：
\[\begin{aligned} \sum_{i=1}^{n}(a_i+x-b_i)^2 &= \sum_{i=1}^{n}(a_i+x)^2+b_i^2-2b_i(a_i+x)\\ &=\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}b_i^2+nx^2-2x(\sum_{i=1}^{n}a_i-\sum_{i=1}^{n}b_i)-2\sum_{i=1}^{n}a_ib_i \end{aligned} \]惊奇的发现，除了最后一项 \(\sum_{i=1}^{n}a_ib_i\) 意外，其他所有项都是确定的！只需要让这一项最大即可得到整个式子最小。如何让这一项最小呢？
设 \(f_i\) 表示上面那个数组以第 \(i\) 个数为开始的时候，得到的答案，然后把 \(b\) 翻转一下（老套路），\(a\) 环变链，直接跑 \(NTT\) 即可。考虑到值域非常小，最后只需要枚举 \(x\) 即可得到答案。
点击查看代码
#include
#include
using namespace std;
typedef long long ll;
const int N=3e5+13,P=998244353,G=3,Gi=332748118;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
int n,m,A[N],B[N],a[N],b[N],r[N];
inline int qpow(int a,int k){int s=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)s=1ll*a*s%P;return s;}
inline void fft(int *f,int limit,int type){
for(int i=0;i>1]>>1)|((i&1)<<(l-1));
fft(a,limit,1),fft(b,limit,1);
for(int i=0;i