进军多项式(三)：Chirp Z-Transform

Chirp Z-Transform

题目传送门
给定一个n次多项式$F(x)$，对于$i=0$到$m$查询$F(c^i)$
$c$为常数。

我们推一下式子，
$$an{s}_i=\sum _{j=0}^{n-1}{f}_j{c}^{ij}$$
注意到：
$ij=C_{i+j}^2-C_i^2-C_j^2$
$$an{s}_i=\sum _{j=0}^{n-1}{f}_j{c}^{C_{i+j}^2-C_i^2-C_j^2}$$
提取$C_i^2$
$$an{s}_i=\sum _{j=0}^{n-1}{f}_j{c}^{C_{i+j}^2-C_i^2-C_j^2}$$
$$an{s}_i=c^{-C_i^2}\sum _{j=0}^{n-1}{f}_j{c}^{C_{i+j}^2-C_j^2}$$
右边的式子只和$j,i+j$有关，差卷积即可。
复杂度$O((n+m)\log (m+n))$

#include
using namespace std;
const int N = 8e6+7;
int w[2][N];
int lim;
typedef long long LL;
const int mod = 998244353;
int Pow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
} 
int G=3,IG=(mod+1)/G;
int o[2];
void init(int n)
{
	lim=1;
	while(lim<=n) lim<<=1;
	o[0]=Pow(G,(mod-1)/lim);
	o[1]=Pow(IG,(mod-1)/lim);
	for(int d=0;d<2;d++)
	{
		w[d][0]=1;
		for(int i=1;i<(lim>>1);i++)
		w[d][i]=1ll*w[d][i-1]*o[d]%mod;
	}
}
inline void DFT(int *f)
{
	for(int k=lim,l=k>>1,r=1;k>=2;k>>=1,l>>=1,r<<=1)
	for(int i=0;i<lim;i+=k)
	for(int j=i,p=0;p<l;j++,p++)
	{
		int u=f[j],v=f[j+l]%mod;
		f[j]=(u+v)%mod;
		f[j+l]=1ll*w[0][p*r]*(u-v+mod)%mod;
	}
} 
inline void IDFT(int *f)
{
	for(int k=2,l=1,r=(lim>>1);k<=lim;k<<=1,l<<=1,r>>=1)
	for(int i=0;i<lim;i+=k)
	for(int j=i,p=0;p<l;j++,p++)
	{
		int u=f[j],v=1ll*w[1][p*r]*f[j+l]%mod;
		f[j]=(u+v)%mod;
		f[j+l]=(u-v+mod)%mod;
	}	
	int inv=Pow(lim,mod-2);
	for(int i=0;i<lim;i++)
	f[i]=1ll*f[i]*inv%mod;
}
int n,m,c;
int f[N],g[N];
inline int C(int x)
{
	return 1ll*x*(x-1)/2%(mod-1);
}
int main()
{
	cin>>n>>c>>m;
	init((n+m-1)<<1);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&f[i]);
		f[i]=1ll*f[i]*Pow(c,mod-1-C(i))%mod;
	}
	for(int i=0;i<n+m;i++)
	g[i]=Pow(c,C(i))%mod;
	reverse(f,f+n);
	DFT(f);DFT(g);
	for(int i=0;i<lim;i++)
	f[i]=1ll*f[i]*g[i]%mod;
	IDFT(f);
	for(int i=0;i<m;i++)
	printf("%lld ",1ll*f[n+i-1]*Pow(c,mod-1-C(i))%mod);

	return 0;
}

例题

任意模数Chirp Z-Transform

把NTT换成MTT或者三模NTT就好了。
但是注意实现的细节，这玩意卡时间也卡空间。

CF1054H Epic Convolution

设$A_i={\sum }_{j=0}[j^2\equiv i\text{(mod 490018)}]a_j$,$B_i={\sum }_{j=0}[j^3\equiv i\text{(mod 490018)}]b_j$
这里上界减一是因为扩展欧拉定理。
那么答案即为
$$\sum _{i=0}^{490017}\sum _{j=0}^{490017}{A}_i{B}_j{c}^{ij}$$
提取$i$，
$$\sum _{i=0}^{490017}{A}_i\sum _{j=0}^{490017}{B}_j{c}^{ij}$$
设$F(x)={\sum }_i{B}_i{x}^i$
那么就是

$$\sum _{i=0}^{490017}{A}_{i}F(c^i)$$
上板子就好了。
但是要写任模。

拓展

$\text{Bluestein’s Algorithm}$