[HNOI2017] 礼物 - 多项式乘法FFT

题意：给定两个 \(n\) 元环，环上每个点有权值，分别为 \(x_i, y_i\)。定义两个环的差值为

\[\sum_{i=0}^{n-1}{(x_i-y_i)^2}
\]

可以旋转其中的一个环，或者将其中一个环的每种权值加上一个数。求最小化的差值。

Solution: 加数只需要加在一个上面即可（假设可以为负），那么差值可以写成

\[\sum_{i=0}^{n-1}{(x_i-y_{i+k}+c)^2}
\]

我们可以将差值定义为旋转位数\(k\)与加数\(c\)的函数，即 \(f(k,c)\) 。我们现在要找的就是二元函数的峰值。展开得

\[f(k,c)=\sum{x_i^2} + \sum{y_i^2} + nc^2 + 2c \sum{x_i} - 2c\sum{y_i} - 2 \sum{x_i y_{(i+k)\%n}}
\]

我们惊喜地发现没有交叉项，即

\[f(k,c) = g(k) + h(c)
\]

那么我们只需要分别最小化两部分即可。

考虑\(g(k)\)，翻转序列\(x\)，这是一个循环卷积的形式。我们可以将序列\(y\)扩增一倍来转化为线性卷积。那么此时

\[g(k) = \sum_{i=0}^{n-1}{x_{n-1-i} y_{i+k}}
\]

对应到多项式乘法上，找\(g(k)\)的最小值，即在幂次为 \([n-1,2n-1)\) 的项中找最大系数即可。

考虑\(h(c)\)，由于\(m \leq 100\)，暴力枚举即可。

#include<bits/stdc++.h>

#define pi acos(-1)

using namespace std;

struct poly {

	typedef complex<double> E;

	int n,m;

	vector <double> c;

	void read(int deg) {

		c.resize(deg+1);

		for(int i=0;i<=deg;i++) scanf("%lf",&c[i]);

	}

	void write() {

		for(int i=0;i<c.size();i++) printf("%lf ",c[i]);

		printf("\n");

	}

	void fft(E *a,int f,int *R){

		for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);

		for(int i=1;i<n;i<<=1){

			E wn(cos(pi/i),f*sin(pi/i));

			for(int p=i<<1,j=0;j<n;j+=p){

				E w(1,0);

				for(int k=0;k<i;k++,w*=wn){

					E x=a[j+k],y=w*a[j+k+i];

					a[j+k]=x+y;a[j+k+i]=x-y;

				}

			}

		}

	}

	void mul(vector<double> A, vector<double> B){

		int *R; E *a,*b; int L=0;

		int _s=(A.size()+B.size()+2)<<5;

		a=(E*)malloc(_s); b=(E*)malloc(_s); R=(int*)malloc(_s);

		memset(a,0,_s);memset(b,0,_s);memset(R,0,_s);

		n=A.size()-1; for(int i=0;i<=n;i++) a[i]=A[i];

		m=B.size()-1; for(int i=0;i<=m;i++) b[i]=B[i];

		m=n+m;for(n=1;n<=m;n<<=1)L++;

		for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));

		fft(a,1,R);fft(b,1,R);

		for(int i=0;i<=n;i++)a[i]=a[i]*b[i];

		fft(a,-1,R);

		c.resize(m+1);

		for(int i=0;i<=m;i++)c[i]=a[i].real()/n;

		free(a); free(b); free(R);

	}

	poly mul(poly pa,poly pb) {

		poly pc; pc.mul(pa.c,pb.c); return pc;

	}

	poly operator * (const poly &pb) {

		poly ret = mul(*this,pb); return ret;

	}

	poly operator *= (const poly &pb) {

		mul(this->c,pb.c); return *this;

	}

};

int n,m,a[100005],b[100005];

int main() {

	ios::sync_with_stdio(false);

	cin>>n>>m;

	for(int i=0;i<n;i++) cin>>a[i];

	for(int i=0;i<n;i++) cin>>b[i];

	long long sx=0,sy=0;

	for(int i=0;i<n;i++) sx+=a[i],sy+=b[i];

	long long px=0,py=0;

	for(int i=0;i<n;i++) px+=a[i]*a[i],py+=b[i]*b[i];

	long long ans = 1e+9;

	for(int i=-100;i<=100;i++) {

		ans = min(ans, n*i*i+2*i*sx-2*i*sy);

	}

	ans += px + py;

	poly x,y;

	x.c.resize(n);

	for(int i=0;i<n;i++) x.c[i]=a[n-i-1];

	y.c.resize(2*n);

	for(int i=0;i<n;i++) y.c[i]=y.c[i+n]=b[i];

	poly z=x*y;

	long long mx=0;

	for(int i=0;i<n;i++) mx=max(mx,(long long)(z.c[n+i-1]+0.5));

	cout<<ans-2*mx<<endl;

}

巴特西

[HNOI2017] 礼物 - 多项式乘法FFT

最新文章

热门文章