传送门

最小化

$$\sum _{i=1}^n(a_i-b_i{)}^2$$

同时增大亮度是没有意义的,可以转化为增大一个数组的亮度,设增大了数组$a$亮度$x$

$\sum _{i=1}^n(a_i-b_i+x{)}^2$

$=\sum _{i=1}^n{a}_i+\sum _{i=1}^n{b}_i^2+n{x}^2+2x\sum _{i=1}^n(a_i-b_i)-2\sum _{i=1}^n{a}_i{b}_i$

假设增加的亮度一定,变化的就只有最后一项,也就是最大化$2\sum _{i=1}^n{a}_i{b}_i$

但是每一种对齐方式都需要计算形如

$$-2(a_1{b}_x+a_2{b}_{x+1}...+a_n{b}_{x-1})$$的式子

这部分已经是$O(n)$的了

但是如果把$a$数组复制一份在最后面是一个长度$2n$的序列

把数组$b$反转,做卷积得到的$k\in [n+1,2n]$项中有

$$c_k=\sum _{i+j==k}{a}_i{b}_j$$

模拟一下$k=n+2$的情况

数组$a_1{a}_2...a_n{a}_1{a}_2...a_n$和$b_n{b}_{n-1}....b_1$卷积

$c_{n+2}=a_2\ast b_1+a_3\ast b_2+a_4\ast b_3...a_1\ast b_{n-1}$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
const int mod = 998244353,G=3,Gi=(mod+1)/3;
int n,m,r[maxn],a[maxn],b[maxn];
int quick(int x,int n)
{
	int ans = 1;
	for( ; n ; n>>=1,x=x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans; 
}
void init(int limit)
{
	for(int i=0;i<limit;i++)	r[i] = ( r[i>>1]>>1 ) | ( (i&1)?limit>>1:0 );
}
void NTT(int *a,int limit,int type )
{
	for(int i=0;i<limit;i++)
		if( i<r[i] )	swap( a[i],a[r[i]] );
	for(int mid=1;mid<limit;mid<<=1 )
	{
		int wn = quick( (type==1)?G:Gi,(mod-1)/(mid<<1));
		for(int R=mid<<1,i=0;i<limit;i+=R)
		for(int w=1,k=0;k<mid;k++,w=w*wn%mod )
		{
			int x = a[i+k], y = a[i+k+mid]*w%mod;
			a[i+k] = (x+y)%mod, a[i+k+mid] = (x-y+mod)%mod;
		}
	}
	if( type==1 )	return;
	int inv = quick(limit,mod-2);
	for(int i=0;i<limit;i++)	a[i] = a[i]*inv%mod;
}
void mul(int *a,int *b,int n,int m)
{
	int limit = 1;
	while( limit<=n+m )	limit<<=1;
	init(limit);
	for(int i=0;i<limit;i++)
	{
		if( i>n )	a[i] = 0;
		if( i>m )	b[i] = 0;
	}
	NTT(a,limit,1); NTT(b,limit,1);
	for(int i=0;i<limit;i++)	a[i] = a[i]*b[i]%mod;
	NTT(a,limit,-1);
}
int prea,preb,ajb,ans=1e9;
signed main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
		a[i+n] = a[i];
	}
	for(int i=1;i<=n;i++)	{ cin >> b[i]; }
	for(int i=1;i<=n;i++)
		prea+=a[i]*a[i],preb+=b[i]*b[i],ajb+=a[i]-b[i];
	for(int l=1,r=n;r>=l;r--,l++)	swap( b[l],b[r] );
	mul(a,b,2*n,n);
	for(int i=-100;i<=100;i++)//给i加上这么多
	for(int j=n+1;j<=2*n;j++)
		ans = min( ans,prea+preb+ajb*2*i+n*i*i-2*a[j] );	
	cout << ans;
}