$ntt$ 入门题。

考虑展开要求的式子∑i=0n−1(xi−yi−c)2\sum_{i=0}^{n-1}(x_i-y_i-c)^2∑i=0n−1​(xi​−yi​−c)2

=>∑i=0n−1(xi2+yi2+c2−2c(xi−yi)−2xiyi)\sum_{i=0}^{n-1}(x_i^2+y_i^2+c^2-2c(x_i-y_i)-2x_iy_i)∑i=0n−1​(xi2​+yi2​+c2−2c(xi​−yi​)−2xi​yi​)

令sum=∑i=0n−1xi−yisum=\sum_{i=0}^{n-1}x_i-y_isum=∑i=0n−1​xi​−yi​

=>(∑i=0n−1(xi2+yi2))+min⁡{nc2−2sum∗c}−2∗max⁡{∑i=0n−1xiyi}(\sum_{i=0}^{n-1}(x_i^2+y_i^2))+\min\{nc^2-2sum*c\}-2*\max\{ \sum_{i=0}^{n-1}x_iy_i\}(∑i=0n−1​(xi2​+yi2​))+min{

nc2−2sum∗c}−2∗max{

∑i=0n−1​xi​yi​}

化到这一步的时候我卡了一下。

考虑第一坨可以直接算，第二坨可以取二次函数对称轴附近求极值。

关键在于第三坨的极值。

这个怎么求呢？

考虑将$b$数组翻转。

这样对$a,b$进行$ntt$，然后得到的新数列{zn}\{z_n\}{

zn​}中的zi+zn+iz_i+z_{n+i}zi​+zn+i​就对应着数列an,bna_n,b_nan​,bn​的一种对齐方法的和。

因此只需要在$ntt$之后给zi+zn+iz_i+z_{n+i}zi​+zn+i​取个$\max$就行了。

代码：

#include
    
     using namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}typedef long long ll;const int mod=998244353,N=2e5+5;int n,m,a[N],b[N],pos[N],ans=0,lim=1,tim=0,mx=0,sum=0;inline int ksm(int a,int p){
    int ret=1;for(;p;p>>=1,a=(ll)a*a%mod)if(p&1)ret=(ll)ret*a%mod;return ret;}inline void ntt(int a[],int type){
    	for(int i=0;i
     
      
       >1,typ=type==1?3:(mod+1)/3;	for(int wn,mid=1;mid
       
        <<=1,mult>>=1){
    		wn=ksm(typ,mult);		for(int len=mid<<1,j=0;j
        
         >1]>>1)|((i&1)<<(tim-1));	ntt(a,1),ntt(b,1);	for(int i=0;i