@[提动Crazy](/user/178519) 让我感到迷惑的是，最后的判断明明可以 $\Theta(1)$，为什么偏偏要 $\Theta(nm)$ 呢？
by NaCly_Fish @ 2020-04-02 00:54:53
您可以看一下，这是我的写法
```cpp
for(int i=0;i!=n;++i) read(a[i]);
for(int i=0;i!=n;++i) read(b[i]);
for(int i=0;i!=n;++i){
ans += a[i]*a[i]+b[i]*b[i];
k += a[i]-b[i];
}
reverse(a,a+n);
memcpy(a+n,a,n<<2);
int lim = 1<<(32-__builtin_clz(n*3));
dft(a,lim),dft(b,lim);
for(int i=0;i!=lim;++i) a[i] = (ll)a[i]*b[i]%p;
idft(a,lim);
int tmp = 0;
for(reg int i=n;i!=(n<<1);++i) tmp = max(tmp,a[i]);
ans -= tmp<<1,x = -k/n;
tmp = 1<<30;
for(int i=x-2;i<=x+2;++i) tmp = min(tmp,i*(n*i+(k<<1)));
ans += tmp;
printf("%d",ans);
```
by NaCly_Fish @ 2020-04-02 00:57:28
神鱼！
by impuk @ 2020-04-02 07:45:33
神鱼！
by Ryo_Yamada @ 2020-04-02 07:51:46
谢谢神鱼
by tidongCrazy @ 2020-04-02 08:01:19