说明

本题要求解密由TN设计的加密方案。给定两个实数序列β和γ，其中γ是通过特定的加密步骤从α和β生成的。我们的目标是恢复原始序列α。加密过程涉及将β反转、旋转后与α进行卷积运算。解密过程需要逆向操作，利用快速傅里叶变换（FFT）来高效求解。

算法标签

• 快速傅里叶变换（FFT）：用于高效计算卷积和逆卷积
• 复数运算：处理实数序列的变换
• 数学推导：理解加密和解密的数学关系

解题思路

1. 问题分析：

   • 序列γ是通过将β反转、旋转后与α进行卷积生成的。
   • 解密需要从γ和β中恢复α，这可以通过FFT实现高效的卷积和逆卷积运算。

2. 关键步骤：

   • 对序列β和γ进行FFT变换。
   • 在频域中求解α的FFT变换。
   • 对结果进行逆FFT变换得到时域的α序列。

3. 算法选择：

   • 使用FFT加速卷积运算。
   • 利用复数运算处理实数序列的变换。
   • 通过数学推导建立β、γ和α之间的关系式。

分析

1. FFT变换：

   • 将β和γ转换到频域，便于进行卷积运算。
   • 频域中的乘法对应时域中的卷积。

2. 频域求解：

   • 在频域中，α的FFT可以通过γ的FFT除以β的FFT得到。
   • 需要考虑零点和数值稳定性。

3. 逆FFT变换：

   • 将频域结果转换回时域，得到序列α。
   • 对结果进行四舍五入，保留四位小数。

实现步骤

1. 输入处理：

   • 读取序列长度n。
   • 读取序列β和γ的数值。

2. FFT变换：

   • 对β和γ进行FFT变换。
   • 初始化FFT所需的参数和临时数组。

3. 频域运算：

   • 在频域中计算α的FFT。
   • 处理复数除法和数值稳定性。

4. 逆FFT变换：

   • 对结果进行逆FFT变换。
   • 调整结果并四舍五入。

5. 输出结果：

   • 输出恢复的序列α，保留四位小数。

代码解释

• 复数运算：定义了复数的加减乘除运算，支持FFT所需的操作。
• FFT实现：包括FFT和逆FFT的实现，以及初始化函数。
• Bluestein算法：用于处理非2的幂次长度的FFT。
• 主函数：读取输入，调用FFT和逆FFT，输出结果。

该方法通过FFT高效地解决了卷积和逆卷积问题，确保在合理时间内恢复原始序列α。

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define cs const

cs double PI=acos(-1);
struct Complex{
	double x,y;
	Complex(){}
	Complex(cs double &_x,cs double &_y):x(_x),y(_y){}
	Complex conj()cs{return Complex(x,-y);}
	friend Complex operator+(cs Complex &a,cs Complex &b){return Complex(a.x+b.x,a.y+b.y);}
	friend Complex operator-(cs Complex &a,cs Complex &b){return Complex(a.x-b.x,a.y-b.y);}
	friend Complex operator*(cs Complex &a,cs Complex &b){return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
	friend Complex operator/(cs Complex &a,cs double &b){return Complex(a.x/b,a.y/b);}
	friend Complex operator/(cs Complex &a,cs Complex &b){return a*b.conj()/(b.x*b.x+b.y*b.y);}
};

cs int N=1<<17|1;

int r[N<<2|1];
Complex w[N<<2|1];
inline void FFT(Complex *A,int len,int typ){
	if(typ==-1)std::reverse(A+1,A+len);
	for(int re i=0;i<len;++i)if(i<r[i])std::swap(A[i],A[r[i]]);
	for(int re i=1;i<len;i<<=1)
	for(int re j=0;j<len;j+=i<<1)
	for(int re k=0;k<i;++k){
		static Complex x,y;
		x=A[j+k],y=A[j+k+i]*w[len/i/2*k];
		A[j+k]=x+y;
		A[j+k+i]=x-y;
	}
	if(typ==-1)for(int re i=0;i<len;++i)A[i]=A[i]/len;
}
inline void init_rev(int len){
	static int last;if(last==len)return ;last=len;
	for(int re i=0;i<len;++i)
	r[i]=r[i>>1]>>1|((i&1)*(len>>1)),
	w[i]=Complex(cos(2*PI*i/len),sin(2*PI*i/len));
}

inline void BS(Complex *a,int l,int typ){
	static Complex A[N<<2|1],B[N<<2|1];
	int l2=l<<1;
	for(int re i=0;i<l;++i)A[i]=a[i]*Complex(cos(PI*i*i/l),typ*sin(PI*i*i/l));
	for(int re i=0;i<l2;++i)B[i]=Complex(cos(PI*(i-l)*(i-l)/l),-typ*sin(PI*(i-l)*(i-l)/l));
	int len=1;while(len<l*3)len<<=1;
	for(int re i=l;i<len;++i)A[i]=Complex(0,0);
	for(int re i=l2;i<len;++i)B[i]=Complex(0,0);
	init_rev(len);
	FFT(A,len,1),FFT(B,len,1);
	for(int re i=0;i<len;++i)A[i]=A[i]*B[i];
	FFT(A,len,-1);
	for(int re i=0;i<l;++i)a[i]=A[i+l]*Complex(cos(PI*i*i/l),typ*sin(PI*i*i/l));
	if(typ==-1)for(int re i=0;i<l;++i)a[i]=a[i]/l;
}

int n;
Complex a[N],b[N],c[N];

signed main(){
	scanf("%d",&n);
	for(int re i=0;i<n;++i)scanf("%lf",&b[i].x);
	for(int re i=0;i<n;++i)scanf("%lf",&c[i].x);
	BS(b,n,1),BS(c,n,1);
	for(int re i=0;i<n;++i)a[i]=c[i]/b[i];
	BS(a,n,-1);
	for(int re i=0;i<n;++i)printf("%.4f\n",a[i].x);
	return 0;
}