推导
[f(c^i)=sum_{j=0}^{n-1}a_jc^{ij}
]
[ij={i+jchoose 2}-{ichoose 2}-{jchoose 2}
]
[egin{aligned}
f(c^i)&=sum_{j=0}^{n-1}a_jc^{{i+jchoose 2}-{ichoose 2}-{jchoose 2}}\
&=c^{-{ichoose 2}}sum_{j=0}^{n-1}a_jc^{-{jchoose 2}}c^{i+jchoose 2}
end{aligned}
]
Code
#include <bits/stdc++.h>
using std::swap; using std::reverse;
const int N = 1000005, M = 40005, P = 998244353, inv2 = P+1>>1;
int n, c, m, L, a[N*4], b[N*4];
int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int qpow(int a, int b) {
int t = 1;
for (; b; b >>= 1, a = 1LL * a * a % P)
if (b & 1) t = 1LL * t * a % P;
return t;
}
int W[N*4], pw[N*4], ipw[N*4];
void prework(int n) {
for (int i = 1; i < n; i <<= 1)
for (int j = W[i] = 1, Wn = qpow(3, (P-1)/i>>1); j < i; j++)
W[i+j] = 1LL * W[i+j-1] * Wn % P;
pw[0] = ipw[0] = pw[1] = ipw[1] = 1; pw[2] = c, ipw[2] = qpow(c, P-2);
for (int i = 3; i < n; i++)
pw[i] = 1LL * pw[i-1] * pw[2] % P, ipw[i] = 1LL * ipw[i-1] * ipw[2] % P;
for (int i = 3; i < n; i++)
pw[i] = 1LL * pw[i-1] * pw[i] % P, ipw[i] = 1LL * ipw[i-1] * ipw[i] % P;
}
void fft(int *a, int n, int op) {
static int rev[N*4] = {0};
for (int i = 1; i < n; i++)
if ((rev[i] = rev[i>>1]>>1|(i&1?n>>1:0)) > i) swap(a[i], a[rev[i]]);
for (int q = 1; q < n; q <<= 1)
for (int p = 0; p < n; p += q << 1)
for (int i = 0, t; i < q; i++)
t = 1LL * W[q+i] * a[p+q+i] % P, a[p+q+i] = inc(a[p+i], P-t), a[p+i] = inc(a[p+i], t);
if (op) return;
for (int i = 0, inv = qpow(n, P-2); i < n; i++) a[i] = 1LL * a[i] * inv % P;
reverse(a + 1, a + n);
}
int getsz(int n) { int x = 1; while (x < n) x <<= 1; return x; }
int main() {
scanf("%d%d%d", &n, &c, &m);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int L = getsz(n + m); prework(L);
for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * ipw[i] % P;
reverse(a, a + n + 1);
for (int i = 0; i < n + m; i++) b[i] = pw[i];
fft(a, L, 1), fft(b, L, 1);
for (int i = 0; i < L; i++) a[i] = 1LL * a[i] * b[i] % P;
fft(a, L, 0);
for (int i = 0; i < m; i++) printf("%d ", 1LL * a[n + i] * ipw[i] % P);
return 0;
}