专栏文章

题解 P6800 【【模板】Chirp-Z Transform】

ss_r_fNOI RP++
P6800题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mkepidzm
此快照首次捕获于
2026/01/15 08:23
2 个月前
此快照最后确认于
2026/01/15 08:23
2 个月前
查看原文
ansi=F(ci)=∑j=0n−1ajcijans_i = F(c^i) = \sum\limits_{j=0}^{n-1} a_jc^{ij}
众所周知, ij=(i+j2)−(i2)−(j2)ij = \binom{i+j}{2} - \binom{i}{2} - \binom{j}{2} :
ansi=c−(i2)∑j=0n−1ajc−(j2)c(i+j2)ans_i = c^{-\binom{i}{2}} \sum\limits_{j=0}^{n-1} a_jc^{-\binom{j}{2}} c^{\binom{i+j}{2}}
不难发现这是一个卷积形式，模数 998244353998244353 为 NTT 模数, NTT 即可。
几个细节：
1.1. 注意到我们是把一个长度为 n+mn+m 的多项式和 长度为 nn 的多项式做卷积，但是我们只需要卷积结果的第 n−(n+m−1)n - (n+m-1) 项,由于 NTT 是循环卷积，所以我们可以把多项式长度设为 n+mn+m , 对答案没有影响。
2.2. 每次用快速幂算 c−(i2)c^{-\binom{i}{2}} 和 c(i2)c^{\binom{i}{2}} 是Θ((n+m)log⁡mod)\Theta((n+m)\log mod) 的,非常慢。
可以 Θ(mod)\Theta(\sqrt{mod}) 预处理然后光速幂 Θ(1)\Theta(1) 查询,或者用两次前缀积直接递推结果.
code(最慢的点324ms) :
CPP
#include <bits/stdc++.h>
#define LL unsigned long long
#define uint unsigned int
using namespace std;
template <typename T> void read(T &x){
	static char ch; x = 0,ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int P = 998244353,N = 1<<21;
inline uint power(uint x,int y){
	y %= P-1;
	static uint r; r = 1; while (y){ if (y&1) r = (LL)r * x % P; x = (LL)x * x % P,y >>= 1; }
	return r;
}
int n,m,c,R[N],L; uint a[N],w[N<<1],iw[N<<1],pwc[N],ipwc[N],F[N],G[N];
inline int getR(int n){
	int i,l = 1,Lim = 2; while (Lim <= n) Lim <<= 1,++l;
	for (i = 0; i < Lim; ++i) R[i] = (R[i>>1]>>1) | ((i&1)<<l-1);
	return Lim;
}
inline void NTT(uint *A,int n){
	register int i,j,k; uint v;
	for (i = 1; i < n; ++i) if (i < R[i]) swap(A[i],A[R[i]]);
	for (i = 1; i < n; i <<= 1) for (j = 0; j < n; j += i << 1) for (k = j; k < i+j; ++k)
		v = (LL)A[k+i] * w[(i<<1)+k-j] % P,A[k+i] = (A[k]<v)?(A[k]+P-v):(A[k]-v),A[k] = (A[k]+v>=P)?(A[k]+v-P):(A[k]+v);
}
inline void iNTT(uint *A,int n){
	register int i,j,k; uint v;
	for (i = 1; i < n; ++i) if (i < R[i]) swap(A[i],A[R[i]]);
	for (i = 1; i < n; i <<= 1) for (j = 0; j < n; j += i << 1) for (k = j; k < i+j; ++k)
		v = (LL)A[k+i] * iw[(i<<1)+k-j] % P,A[k+i] = (A[k]<v)?(A[k]+P-v):(A[k]-v),A[k] = (A[k]+v>=P)?(A[k]+v-P):(A[k]+v);
	for (i = 0,v = power(n,P-2); i < n; ++i) A[i] = (LL)A[i] * v % P;
}
int main(){
	register int i,j; uint v;
	read(n),read(c),read(m);
	pwc[1] = c,ipwc[1] = power(c,P-2);
	for (pwc[0] = i = 1; i <= n+m; ++i) pwc[i] = (LL)pwc[i-1] * pwc[1] % P;
	for (pwc[0] = i = 1; i <= n+m; ++i) pwc[i] = (LL)pwc[i] * pwc[i-1] % P;
	for (ipwc[0] = i = 1; i <= max(n,m); ++i) ipwc[i] = (LL)ipwc[i-1] * ipwc[1] % P;
	for (ipwc[0] = i = 1; i <= max(n,m); ++i) ipwc[i] = (LL)ipwc[i] * ipwc[i-1] % P;
	for (i = 0; i < n; ++i) read(a[i]),a[i] = (LL)a[i] * (i?ipwc[i-1]:1) % P;
	L = getR(n+m);
	for (i = 1,j = 2; j <= L; ++i,j <<= 1){
		int l = j + (j>>1);
		w[j] = 1,v = power(3,(P-1)/j);
		for (register int k = j+1; k <= l; ++k) w[k] = (LL)w[k-1] * v % P;
		iw[j] = 1,v = power(v,P-2);
		for (register int k = j+1; k <= l; ++k) iw[k] = (LL)iw[k-1] * v % P;
	}
	for (F[0] = 1,i = 1; i <= n+m; ++i) F[i] = pwc[i-1];
	for (i = 1; i <= n; ++i) G[i] = a[n-i];
	NTT(F,L); NTT(G,L);
	for (i = 0; i < L; ++i) F[i] = (LL)F[i] * G[i] % P;
	iNTT(F,L);
	for (i = 0; i < m; ++i) write((LL)F[i+n] * (i?ipwc[i-1]:1) % P),putchar(i<m?' ':'\n');
	return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...