题解 P6800 【【模板】Chirp-Z Transform】
s_r_f
·
·
题解
ans_i = F(c^i) = \sum\limits_{j=0}^{n-1} a_jc^{ij}
众所周知, ij = \binom{i+j}{2} - \binom{i}{2} - \binom{j}{2} :
ans_i = c^{-\binom{i}{2}} \sum\limits_{j=0}^{n-1} a_jc^{-\binom{j}{2}} c^{\binom{i+j}{2}}
不难发现这是一个卷积形式，模数 998244353 为 NTT 模数, NTT 即可。
几个细节：
$2.$ 每次用快速幂算 $c^{-\binom{i}{2}}$ 和 $c^{\binom{i}{2}}$ 是$\Theta((n+m)\log mod)$ 的,非常慢。
可以 $\Theta(\sqrt{mod})$ 预处理然后光速幂 $\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;
}
```