多项式学习笔记

前言：菜狗痛改前非决定认真学习多项式。

礼物

大意：

给定两个环形矩阵A，B，现在可以对A矩阵统一加上某一个值，并将其任意旋转，求操作过后的最小值。

思路：

算是一道多项式板子题了。首先考虑将a[i]加上一个值x，那么原来的式子就可以转化为

如果我们把x看做是自变量的话，这其实就是一个关于x的二次函数，那么求它的最小值不是轻轻松松嘛，而且我们发现跟x有关的项的系数都是定值，所以x的确定值是可以直接得到的。最后，我们就只需要求最后一项的最大值就可以了。

怎么求呢，如果我们把a数组倒过来的话，那么原式就可以转化为

,那么这不就是一个卷积的形式嘛，最后考虑到a数组可以任意旋转，我们就只需要将其扩大到原来的两倍然后去卷积，最后在第n+1项到第n*2项之间取最大值就可以了。

卷积的话可以用fft，当然其实极限情况下中间变量也不会超过998244353，所以用ntt也是可以的。

算是一道比较温柔的推柿子题了。

（ps：c++是默认向0取整的，但是我们对正负情况的取整方向是不一样的，所以我们要分类讨论）

code：

#include
using namespace std;
#define ll long long
#define IL inline
#define ull unsigned long long
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int _G=3,mod=998244353,Maxn=1e5+10;
namespace FastIOT{
	const int bsz=1<<18;
	char bf[bsz],*hed,*tail;
	inline char gc(){if(hed==tail)tail=(hed=bf)+fread(bf,1,bsz,stdin);if(hed==tail)return 0;return *hed++;}
	template<typename T>IL void read(T &x){T f=1;x=0;char c=gc();for(;c>'9'||c<'0';c=gc())if(c=='-')f=-1;
	for(;c<='9'&&c>='0';c=gc())x=(x<<3)+(x<<1)+(c^48);x*=f;}
	template<typename T>IL void print(T x){if(x<0)putchar(45),x=-x;if(x>9)print(x/10);putchar(x%10+48);}
	template<typename T>IL void println(T x){print(x);putchar('\n');}
}
using namespace FastIOT;
int F[Maxn<<2],FF[Maxn<<2],G[Maxn<<2],n,m;
int pfa,pfb,det;
ll powM(ll a,ll t=mod-2)
{
    ll ans=1;
    while(t)
    {
    	if(t&1)ans=ans*a%mod;
    	a=a*a%mod;t>>=1;
    }
	return ans;
}
const int invG=powM(_G);
int tr[Maxn<<2],tf;
void tpre(int n)
{
  	if (tf==n)return ;tf=n;
  	for(int i=0;i
    tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
}
void NTT(int *g,bool op,int n)
{
    tpre(n);
    static ull f[Maxn<<2],w[Maxn<<2]={1};
    for (int i=0;i5)+g[tr[i]])%mod;
    for(int l=1;l1)
    {
    	ull tG=powM(op?_G:invG,(mod-1)/(l+l));
    	for (int i=1;i-1]*tG%mod;
    	for(int k=0;k
        for(int p=0;p
	    {
	        int tt=w[p]*f[k|l|p]%mod;
	        f[k|l|p]=f[k|p]+mod-tt;
	        f[k|p]+=tt;
        }      
    	if (l==(1<<10)) for (int i=0;i
    }
    if (!op)
    {
    	ull invn=powM(n);
    	for(int i=0;i
        g[i]=f[i]%mod*invn%mod;
    }
    else for(int i=0;i
}
void px(int *f,int *g,int n)
{for(int i=0;i1ll*f[i]*g[i]%mod;}
void times(int *f,int *g,int len,int lim)
{
    static int sav[Maxn<<2];
    int n=1;for(n;n1);
    clr(sav,n);cpy(sav,g,n);
    NTT(f,1,n);NTT(sav,1,n);
    px(f,sav,n);NTT(f,0,n);
    clr(f+lim,n-lim);clr(sav,n);
}
void solve()
{
	read(n);read(m); 
	//cout<
	for(int i=0;i
	{
		read(FF[i]);
		pfa+=FF[i]*FF[i];
	}
	
	for(int i=0;i
	{
		read(G[i]);
		pfb+=G[i]*G[i];
		det+=FF[i]-G[i];  
	}
	
	for(int i=0;i
	{
		F[i]=FF[n-i-1];
		F[n+i]=F[i];
	}
	
	times(F,G,n*2,n*3);
	ll ma=0;
	for(int i=n;i2;++i) ma=max(ma,(ll)F[i]);
	ma<<=1;
	det<<=1;
	double xx=-1.0*det/n/2.000;
	if(xx>0) xx=(ll)(xx+0.5);
	else xx=(ll)(xx-0.5);
	//printf("%d %f\n",det,xx);
	ll ans=0;
	ans+=pfa+pfb+xx*xx*n+det*xx;
	ans-=ma;
	printf("%lld\n",ans);
}
int main()
{
	//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}