fft

我去，听说洛谷博客要挂了，紧急进行一个家的搬

救命，怎么这么丑！（

快速傅里叶变换

离散傅里叶变换（DFT）的优化版，用于加速卷积。

我们有两个 \(n\) 项式：

\(A(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n\) .

\(B(x)=b_0+b_1x+b_2x^2+\dots+b_nx^n\) .

现在要求出 \(C(x)=A(x)\times B(x)\) .

离散傅里叶变换

多项式的表达方式有两种，系数表示法和点值表示法。

系数表示法be like: \(f(x)=\{a_0,a_1,a_2,\dots,a_n\}\) .

朴素求 \(C(x)\) 就是用系数表示法进行一个计算，即将 \(A\) 的每个系数与 \(B\) 的每个系数进行一个相乘的操作，然后再同次项系数相加，这样我们就得到了\(O(n^2)\)的复杂度。

点值表示法是选取 \(n\) 个插入值 \(x_0,x_1,x_2...x_n\) ，那么 \(f(x)\) 还可以用 \(f(x)=\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),\dots,(x_n,f(x_n))\}\) 表示。

引理：

一个 \(n\) 项式在 \(n+1\) 个点的不同取值唯一确定了该多项式。

使用点值表示法表示 \(A\) 和 \(B\) ，则 \(C\) 可以表示为 \(C(x)=\{(x_0,A(x_0)B(x_0)),(x_1,A(x_1)B(x_1)),\dots,(x_n,A(x_n)B(x_n))\}\) .

计算 \(O(n^2)\) ，枚举 \(O(n)\) .

快速傅里叶变换

考虑如何优化将原多项式由系数表示法转化为点值表示法，我们可以选择特殊的 \(x_i\) 的取值，如满足 \(\omega^k=1\) 的 \(\omega\) .

在实数-虚数轴上，以原点为圆心，1为半径画一个圆，圆上所有点都满足这个性质。

将其 \(n\) 等分后，从 \((1,0)\) 开始顺时针从\(0\)标号，记 \(\omega_n^k\) 为标号为 \(k\) 的点所代表的复数值。由模长相乘，极角相加可得\((\omega_n^1)^k=\omega_n^k\)，其中 \(\omega_n^1\) 被称为 \(n\) 次单位根。

引理：

\(\omega_n^k=\omega_{2n}^{2k}\)
\(\omega_n^{k+\frac{n}{2}}=-\omega_n^k\)
\(\omega_n^n=\omega_0^0\)

显然这仍是 \(O(n^2)\) 的复杂度，考虑分治。

你有一个多项式 \(A(x)=a_0+a_1x+a_2x^2+\dots+a_{n-1}x^{n-1}\) ，按下标奇偶性将其分为两部分，奇部分提一个 \(x\) ，即：

\(A(x)=a_0+a_2x^2+a_4x^4+\dots+a_{n-2}x^{n-2}+x(a_1+a_3x^2+\dots+a_{n-1}x^{n-2})\)

设：

\(A_1(x)=a_0+a_2x+a_4x^2+\dots+a_{n-2}x^{\frac{n}{2}-1}\)

\(A_2(x)=a_1+a_3x_1+a_5x^2+\dots+a_{n-1}x^{\frac{n}{2}-1}\)

显然\(A(x)=A_1(x^2)+xA_2(x^2)\).

设 \(k<\frac{n}{2}\) ，将 \(\omega_n^k\) 作为 \(x\) 代入 \(A(x)\) ，则有：

\(A\left(\omega_n^k\right)=A_1\left((\omega_n^k)^2\right)+\omega_n^k A_2\left((\omega_n^k)^2\right)\)

\(=A_1\left(\omega_n^{2k}\right)+\omega_n^kA_2\left(\omega_n^{2k}\right)\)

\(=A_1\left(\omega^k_{\frac{n}{2}}\right)+\omega_n^kA_2\left(\omega_\frac{n}{2}^k\right)\)

对于 \(A\left(\omega_n^{k+\frac{n}{2}}\right)\) ，代入 \(\omega_n^{k+\frac{n}{2}}\)，易得 \(A\left(\omega_n^{k+\frac{n}{2}}\right)=A_1\left(\omega_\frac{n}{2}^k\right)-\omega_n^kA_2\left(\omega_\frac{n}{2}^k\right)\).

显然，只要求出 \(A_1(\omega_\frac{n}{2}^k)\) 和 \(A_2(\omega_\frac{n}{2}^k)\) ，就可以同时求出 \(A(\omega_n^k)\) 和 \(A(\omega_n^{k+\frac{n}{2}})\) . 即，每次求出序列前一半的值，就可以得到序列后一半的值，时间复杂度为 \(O(n\log n)\)

#include 

using namespace std;

int read()
{
	int res=0,p=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')p=-1; ch=getchar();}
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return res*p;
}

const int maxn=3e6+10;
const double pi=acos(-1.0);

char s1[maxn],s2[maxn];
int maxx=1,maxl;
int rev[maxn],ans[maxn];

struct note
{
	double real,imag;
	note (double x=0,double y=0) {real=x,imag=y;}
}a[maxn],b[maxn];

note operator * (note x,note y) {return note(x.real*y.real-x.imag*y.imag,x.real*y.imag+x.imag*y.real);}
note operator + (note x,note y) {return note(x.real+y.real,x.imag+y.imag);}
note operator - (note x,note y) {return note(x.real-y.real,x.imag-y.imag);}

void fft(note *x,double flag)
{
	for(int i=0;i>s1>>s2;
	int len1=strlen(s1),len2=strlen(s2);
	for(int i=len1-1;i>=0;--i) a[len1-i-1].real=(double)(s1[i]-'0');
	for(int i=len2-1;i>=0;--i) b[len2-i-1].real=(double)(s2[i]-'0');
	while(maxx>1]>>1)|((i&1)<<(maxl-1));
	fft(a,1),fft(b,1);
	for(int i=0;i<=maxx;++i) a[i]=a[i]*b[i];
	fft(a,-1);
	int tot=0;
	for(int i=0;i<=maxx;++i)
	{
		ans[i]+=(int)(a[i].real/maxx+0.5);
		if(ans[i]>=10) ans[i+1]+=ans[i]/10,ans[i]%=10,maxx+=(i==maxx);
	}
	while(!ans[maxx]&&maxx>=1) --maxx;
	++maxx;
	while(--maxx>=0) cout<