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
|
using namespace std;
typedef long long ll;
const int MAXN = 800010;
const int mod = 998244353, G = 3, Ginv = (998244353 + 1) / 3;
int rev[MAXN];
inline void (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) {
ll 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] = (h1 + h2) % mod;
a[s + p + i] = (h1 - h2 + mod) % 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] = ((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];
}
int *p[MAXN];
int *sta[30], cnt;
int y[MAXN];
void get_p(int now, int l, int r) {
if(l == r) {
p[now] = (int*)malloc(8);
p[now][0] = (mod - l) % mod;
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] = (int*) malloc(sizeof(int[r - l + 2]));
mult(p[now << 1], mid - l + 2, p[now << 1 | 1], r - mid + 1, p[now]);
}
void inter(int now, int l, int r, int *ans) {
if(l == r) {
ans[0] = y[l];
return;
}
cnt++;
if(sta[cnt] == 0) sta[cnt] = (int*)malloc(sizeof(int[r - l + 1]));
int *ans1 = sta[cnt], mid = (l + r) >> 1;
inter(now << 1, l, mid, ans1);
mult(ans1, mid - l + 1, p[now << 1 | 1], r - mid + 1, ans);
inter(now << 1 | 1, mid + 1, r, ans1);
mult(ans1, r - mid, p[now << 1], mid - l + 2, ans1);
add(ans, r - l + 1, ans1, r - l + 1, ans);
cnt--;
}
int n;
int ar[MAXN];
int a[MAXN], pi[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", a + i);
pi[0] = 1;
for(int i = 1; i < n; i++) pi[i] = 1ll * pi[i - 1] * i % mod;
pi[n - 1] = power(pi[n - 1], mod - 2);
for(int i = n - 1; i > 0; i--) pi[i - 1] = 1ll * pi[i] * i % mod;
mult(a, n, pi, n, y);
for(int i = 0, now = 1; i < n; i++) y[i] = 1ll * y[i] * now % mod, now = 1ll * now * (i + 1) % mod;
for(int i = 0; i < n; i++) y[i] = 1ll * y[i] * pi[i] % mod * ((n - i) & 1 ? pi[n - i - 1] : mod - pi[n - i - 1]) % mod;
get_p(1, 0, n - 1);
inter(1, 0, n - 1, ar);
for(int i = 0; i < n; i++) printf("%d ", ar[i]);
puts("");
return 0;
}
|
近期评论