题解 P5383 [模板]普通多项式转下降幂多项式

题面
考虑点值
直接多点求值搞出点值然后卷上一个$e^{-x}$就好了
好像被卡常了,也有可能是打挂了
大佬帮忙康康

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, G = 3, Ginv = (998244353 + 1) / 3;
const int maxn = 400010;
int rev[maxn];
inline int fast(int x) {return x >= mod ? x - mod : x;}
inline void get_rev(int l) {
for(int i = 1; i < (1 << l); i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
inline int power(int a, int b) {
long long res = a, ans = 1;
for(; b; b >>= 1, res = res * res % mod) if(b & 1) ans = ans * res % mod;
return ans;
}
int gg[maxn], ggi[maxn];
inline void ntt(int *a, int l, int type) {
for(int i = 0; i < (1 << l); i++)
if(rev[i] < i) a[i] ^= a[rev[i]] ^= a[i] ^= a[rev[i]];
for(register int p = 1; p < (1 << l); p <<= 1) {
int wn = (type == 1 ? gg[p] : ggi[p]);
for(register int s = 0; s < (1 << l); s += p << 1) {
int w = 1;
for(register int i = 0; i < p; i++) {
int h1 = a[s + i], h2 = 1ll * w * a[s + p + i] % mod;
a[s + i] = fast(h1 + h2);
a[s + p + i] = fast(h1 - h2 + mod);
w = 1ll * w * wn % mod;
}
}
}
if(type == -1) {
int inv = power(1 << l, mod - 2);
for(register int i = 0; i < (1 << l); i++) a[i] = 1ll * a[i] * inv % mod;
}
}
inline void add(int *a, int sizea, int *b, int sizeb, int *c) {
for(register int i = 0; i < max(sizea, sizeb); i++)
c[i] = fast((i < sizea ? a[i] : 0) + (i < sizeb ? b[i] : 0));
}
inline void del(int *a, int sizea, int *b, int sizeb, int *c) {
for(register int i = 0; i < max(sizea, sizeb); i++)
c[i] = fast((i < sizea ? a[i] : 0) - (i < sizeb ? b[i] : 0) + mod);
}
int f[maxn], g[maxn], h[maxn];
inline void mult(int *a, int sizea, int *b, int sizeb, int *c) {
register int l = 0;
for(; (1 << l) < sizea + sizeb - 1; l++);
get_rev(l);
for(register int i = 0; i < (1 << l); i++) {
f[i] = (i < sizea ? a[i] : 0);
g[i] = (i < sizeb ? b[i] : 0);
}
ntt(f, l, 1);
ntt(g, l, 1);
for(int i = 0; i < (1 << l); i++)
f[i] = 1ll * f[i] * g[i] % mod;
ntt(f, l, -1);
for(register int i = 0; i < sizea + sizeb - 1; i++) c[i] = f[i];
}
inline void T(int *a, int sizea, int *b) {
for(int i = 0; i < sizea; i++) b[i] = a[sizea - i - 1];
}
inline void inv(int *a, int sizea, int *b, int sizeb) {
b[0] = power(a[0], mod - 2);
for(int now = 1; now < sizeb; now <<= 1) {
mult(b, now, b, now, h);
mult(h, now * 2 - 1, a, min(sizea, now << 1), h);
for(int i = 0; i < now << 1; i++) {
if(i < now) b[i] = fast(fast(b[i] + b[i]) - h[i] + mod);
else b[i] = fast(mod - h[i]);
}
}
}
inline void der(int *a, int sizea, int *b) {
for(int i = 0; i < sizea - 1; i++) b[i] = 1ll * a[i + 1] * (i + 1) % mod;
}
int ta[maxn], tb[maxn], invtb[maxn];
inline void div(int *a, int sizea, int *b, int sizeb, int *c) {
T(a, sizea, ta);
T(b, sizeb, tb);
inv(tb, sizeb, invtb, sizea - sizeb + 1);
mult(ta, sizea - sizeb + 1, invtb, sizea - sizeb + 1, ta);
T(ta, sizea - sizeb + 1, c);
}
inline void modu(int *a, int sizea, int *b, int sizeb, int *c) {
div(a, sizea, b, sizeb, h);
mult(b, sizeb, h, sizea - sizeb + 1, h);
for(int i = 0; i < sizeb - 1; i++) {
c[i] = fast(a[i] - h[i] + mod);
}
}
struct POOL {
int buf[3000010], cnt;
inline int* get(int size) {
return buf + (cnt += size) - size;
}
} pool;
int *p[maxn];
int y[100010];
void get_p(int now, int l, int r) {
if(l == r) {
p[now] = pool.get(2);
p[now][0] = fast(mod - l);
p[now][1] = 1;
return;
}
int mid = (l + r) >> 1;
get_p(now << 1, l, mid);
get_p(now << 1 | 1, mid + 1, r);
p[now] = pool.get(r - l + 2);
mult(p[now << 1], mid - l + 2, p[now << 1 | 1], r - mid + 1, p[now]);
}
int *sta[30], cnt;
void get_y(int now, int l, int r, int *a) {
if(l == r) {
y[l] = a[0];
return;
}
cnt++;
if(sta[cnt] == 0) sta[cnt] = pool.get(r - l + 1);
int mid = (l + r) >> 1;
int *aa = sta[cnt];
modu(a, r - l + 1, p[now << 1], mid - l + 2, aa);
get_y(now << 1, l, mid, aa);
modu(a, r - l + 1, p[now << 1 | 1], r - mid + 1, aa);
get_y(now << 1 | 1, mid + 1, r, aa);
cnt--;
}
int n;
int ar[maxn], ans[maxn];
int dinv[maxn], fac[maxn], finv[maxn];
int main() {
for(int i = 1; i < maxn; i <<= 1) gg[i] = power(G, (mod - 1) / 2 / i);
for(int i = 1; i < maxn; i <<= 1) ggi[i] = power(Ginv, (mod - 1) / 2 / i);
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", ar + i);
for(int i = fac[0] = 1; i < n; i++) fac[i] = 1ll * i * fac[i - 1] % mod;
finv[n - 1] = power(fac[n - 1], mod - 2);
for(int i = n - 1; i > 0; i--) finv[i - 1] = 1ll * i * finv[i] % mod;
for(int i = 0; i < n; i++) dinv[i] = i & 1 ? mod - finv[i] : finv[i];
get_p(1, 0, n - 1);
get_y(1, 0, n - 1, ar);
for(int i = 0; i < n; i++) y[i] = 1ll * y[i] * finv[i] % mod;
mult(y, n, dinv, n, ans);
for(int i = 0; i < n; i++) printf("%d%c", ans[i], " \n"[i == n - 1]);
return 0;
}