本文摘要：本文讨论了如何利用快速傅里叶变换（FFT）解决情侣手环装饰物亮度调整问题。在女生生日之际，主人公发现手环拿错，需通过增加自然数c调整单个手环的亮度，并进行旋转操作以减小两个手环的差异值，该差异值定义为各对应位置装饰物亮度差的平方和。运用FFT求解∑SiTi的最大值，并结合二次函数最优化方法确定最小化差异值所需的c值，最终在O(nlogn)的时间复杂度内找到使手环亮度差异最小化的解决方案。

转载文章

本篇文章为转载内容。原文链接：https://blog.csdn.net/P1atform/article/details/79324409。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

标签：FFT

Description

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n，其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手环的 i 号位置装饰物亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)：

∑ni=1(xi−yi)2∑i=1n(xi−yi)2 $\sum_{i=1}^{n}(x_i-y_i)^2$ 麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

Input

输入数据的第一行有两个数n, m，代表每条手环的装饰物的数量为n，每个装饰物的初始亮度小于等于m。

接下来两行，每行各有n个数，分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

1≤n≤50000, 1≤m≤100, 1≤ai≤m

Output

输出一个数，表示两个手环能产生的最小差异值。

注意在将手环改造之后，装饰物的亮度可以大于 m。

不妨设第一个手环为S，第二个手环为T，则题意变为求 $\sum(S_i-T_{i+k}+C)^2$ 的最小值
我们将上式展开，可以得到

\sum (S 2 i + T 2 i + k + C 2 + 2 * C (S i - T i + k) - 2 * S i T i + k)

$\sum(S_i^2+T_{i+k}^2+C^2+2*C(S_i-T_{i+k})-2*S_iT_{i+k})$
进一步得到

\sum S 2 i + \sum T 2 i + n * C 2 + 2 * c * \sum (S i - T i) - 2 * \sum S i T i + k

$\sum S_i^2+\sum T_i^2+n*C^2+2*c*\sum(S_i-T_i)-2*\sum S_iT_{i+k}$
先抛开

CC $C$ 不看，我们发现只有

\sum S_{i} T_{i + k}

$\sum S_iT_{i+k}$ 不是常数
如何求

∑SiTi+k∑SiTi+k $\sum S_iT_{i+k}$ 最大值呢？标准套路：将T数组反转，求出S与T的卷积，不难发现，

∑SiTi+k∑SiTi+k $\sum S_iT_{i+k}$ 对应每一个k的取值，都是卷积中两个相差n次的项的系数之和，这里可以用FFT，将复杂度降到O(nlogn)。
求完

∑SiTi+k∑SiTi+k $\sum S_iT_{i+k}$ 最大值后，我们发现只有关于C的二次项与一次项，直接用二次函数求最值的方法即可，注意C只能为整数。

/**************************************************************Problem: 4827User: P1atformLanguage: C++Result: AcceptedTime:592 msMemory:9108 kb
****************************************************************/#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 200000
#define INF 1000000000
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
ll n,m,M,p=0ll,q=0ll,z=0ll,ans=INF,r[N+50],x,l;
struct com
{double x,y;inline com operator +(com b){com ret;ret.x=x+b.x,ret.y=y+b.y;return ret;}inline com operator -(com b){com ret;ret.x=x-b.x,ret.y=y-b.y;return ret;}inline com operator *(com b){com ret;ret.x=x*b.x-y*b.y,ret.y=x*b.y+y*b.x;return ret;}
}s[N+50],t[N+50]; 
template<class _T> inline void read(_T &x)
{x=0;char ch=getchar();int f=0;while (!isdigit(ch)) {if (ch=='-') f=1;ch=getchar();}while (isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();if (f) x=-x; 
} 
inline void fft(com a[],int k)
{for (int i=1;i<n;i++) if (i<r[i]) swap(a[i],a[r[i]]);for (int i=1;i<n;i<<=1){com w,wn,X,Y;wn.x=cos(pi/i),wn.y=k*sin(pi/i);for (int j=0;j<n;j+=(i<<1)){w.x=1,w.y=0;for (int _=0;_<i;_++,w=w*wn){X=a[j+_],Y=w*a[j+_+i];a[j+_]=X+Y,a[j+_+i]=X-Y;} } }if (k==-1) for (int i=0;i<n;i++) a[i].x/=n;
}
int main()
{read(n),n--,read(M),memset(s,0,sizeof(s)),memset(t,0,sizeof(t));for (int i=0;i<=n;i++) read(x),p+=x*x,q+=x,s[i].x=x;for (int i=0;i<=n;i++) read(x),p+=x*x,q-=x,t[n-i].x=x;for (m=2*n,n=1;n<=m;n<<=1) l++;for (int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));fft(s,1),fft(t,1);for (int i=0;i<=n;i++) s[i]=s[i]*t[i];fft(s,-1),n=m/2,z=(ll)(s[n].x+0.5);for (int i=1;i<=n;i++) z=max(z,(ll)(s[i-1].x+0.5)+(ll)(s[i+n].x+0.5));for (int i=-M;i<=M;i++) ans=min(ans,p-2*z+i*((n+1)*i+2*q));printf("%lld\n",ans);
}

本篇文章为转载内容。原文链接：https://blog.csdn.net/P1atform/article/details/79324409。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

名词解释

作为当前文章的名词解释，仅对当前文章有效。

快速傅里叶变换（FFT）：快速傅里叶变换是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法，广泛应用于信号处理、图像处理、数据压缩等领域。在本文的情侣手环装饰物亮度匹配问题中，通过将问题转化为求解两个序列卷积的最大值，并利用FFT进行快速卷积计算，能够在O(nlogn)的时间复杂度内找到最优解，从而有效地调整一个手环上装饰物的亮度以最小化两个手环之间的差异值。

卷积（Convolution）：在数学和信号处理领域，卷积是两个函数通过翻转其中一个函数并将它们滑动重叠来计算新函数的过程。在本文中，卷积用于求解情侣手环装饰物亮度序列Si与Ti之间相关系数的最大值，即∑SiTi的最大值。通过将第二个序列Ti反转并应用FFT进行卷积运算，可以快速得到所有可能位置下两个序列元素乘积之和，进而确定最佳旋转角度以减小差异值。

二次函数最优化方法：二次函数最优化是指在给定约束条件下，寻找二次函数（变量的平方项及一次项构成的函数）的极小值或极大值的过程。在本问题中，经过FFT计算得出∑SiTi+k的最大值后，剩下的关于调整亮度增量C的表达式是一个二次函数。通过标准的二次函数求极值方法（求导数并令其等于零），结合C必须为自然数这一条件，可以确定使手环亮度差异值达到最小所需的亮度增量C的具体值。