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
| #include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
namespace Poly {
const int mod = 998244353;
inline int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
inline int sub(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(int x, int y) { return (int)((ll)x * y % mod); }
inline int Get(int x) { int ss = 1; for(; ss <= x; ss <<= 1); return ss; }
inline int ksm(int x, int y = mod - 2) {
int ss = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ss = mul(ss, x);
return ss;
}
void ntt(vector<int> &A, int lmt, int opt) {
A.resize(lmt + 5);
for(int i = 0, j = 0; i < lmt; i++) {
if(i > j) swap(A[i], A[j]);
for(int k = lmt >> 1; (j ^= k) < k; k >>= 1);
}
vector<int> w(lmt >> 1);
for(int mid = 1; mid < lmt; mid <<= 1) {
w[0] = 1;
int w0 = ksm(opt == 1 ? 3 : (mod + 1) / 3, (mod - 1) / mid / 2);
for(int j = 1; j < mid; j++) w[j] = mul(w[j - 1], w0);
for(int R = mid << 1, j = 0; j < lmt; j += R)
for(int k = 0; k < mid; k++) {
int x = A[j + k], y = mul(w[k], A[j + mid + k]);
A[j + k] = add(x, y), A[j + mid + k] = sub(x, y);
}
}
if(opt == -1)
for(int i = 0, inv = ksm(lmt); i < lmt; i++) A[i] = mul(A[i], inv);
}
vector<int> Add(const vector<int> &a, const vector<int> &b) {
vector<int> res(Max(a.size(), b.size()));
for(int i = 0; i < res.size(); i++) {
if(i < a.size()) res[i] = add(res[i], a[i]);
if(i < b.size()) res[i] = add(res[i], b[i]);
}
return res;
}
vector<int> Mul(const vector<int> &a, const vector<int> &b) {
vector<int> A = a, B = b; int lmt = Get(a.size() + b.size() - 2);
ntt(A, lmt, 1), ntt(B, lmt, 1);
for(int i = 0; i < lmt; i++) A[i] = mul(A[i], B[i]);
ntt(A, lmt, -1); return A.resize(a.size() + b.size() - 1), A;
}
vector<int> Inv(const vector<int> &A, int sz = -1) {
if(sz == -1) sz = A.size();
vector<int> res; if(sz == 1) return res.pb(ksm(A[0])), res;
res = Inv(A, (sz + 1) / 2);
vector<int> tmp(A.begin(), A.begin() + sz);
int lmt = Get(sz * 2 - 2);
ntt(tmp, lmt, 1), ntt(res, lmt, 1);
for(int i = 0; i < lmt; i++)
res[i] = mul(sub(2, mul(res[i], tmp[i])), res[i]);
ntt(res, lmt, -1); return res.resize(sz), res;
}
vector<int> Sqrt(const vector<int> &A, int sz = -1) {
if(sz == -1) sz = A.size();
vector<int> res; if(sz == 1) return res.pb(1), res;
res = Sqrt(A, (sz + 1) / 2);
vector<int> tmp(A.begin(), A.begin() + sz);
res.resize(sz), res = Add(res, Mul(tmp, Inv(res)));
for(int i = 0; i < res.size(); i++)
res[i] = (res[i] & 1) ? ((res[i] + mod) / 2) : (res[i] / 2);
return res.resize(sz), res;
}
void Div(const vector<int> &A, const vector<int> &B, vector<int> &D, vector<int> &R) {
if(B.size() > A.size()) return (void)(D.clear(), D.pb(0), R = A);
vector<int> a = A, b = B, iB; int n = A.size(), m = B.size();
reverse(a.begin(), a.end()), reverse(b.begin(), b.end());
b.resize(n - m + 1), iB = Inv(b, n - m + 1);
D = Mul(a, iB), D.resize(n - m + 1), reverse(D.begin(), D.end());
R = Mul(B, D);
for(int i = 0; i < m - 1; i++) R[i] = (mod + A[i] - R[i]) % mod;
R.resize(m - 1);
}
vector<int> Ln(const vector<int> &A) {
vector<int> f, g = Inv(A); f.resize(A.size());
for(int i = 1; i < f.size(); i++) f[i - 1] = mul(i, A[i]);
f[f.size() - 1] = 0, f = Mul(f, g), f.resize(A.size());
for(int i = f.size() - 1; i > 0; i--) f[i] = mul(f[i - 1], ksm(i));
f[0] = 0; return f;
}
vector<int> Exp(const vector<int> &A, int sz = -1) {
if(sz == -1) sz = A.size();
vector<int> res; if(sz == 1) return res.pb(1), res;
res = Exp(A, (sz + 1) / 2), res.resize(sz); vector<int> tmp = Ln(res);
for(int i = 0; i < tmp.size(); i++) tmp[i] = add(sub(0, tmp[i]), A[i]);
tmp[0] = add(1, tmp[0]), res = Mul(res, tmp);
return res.resize(sz), res;
}
vector<int> Ksm(const vector<int> &A, const vector<int> &K) {
vector<int> res = Ln(A); int k = 0;
for(int i = 0; i < K.size(); i++) k = add(mul(k, 10), K[i]);
for(int i = 0; i < res.size(); i++) res[i]= mul(res[i], k);
res = Exp(res), res.resize(A.size()); return res;
}
}
const int N = 200010;
int n, m;
char s[N];
vector<int> a, b;
int main() {
scanf("%d%s", &n, &s);
for(int i = 0, ed = strlen(s); i < ed; i++) b.pb(s[i] - '0');
for(int i = 0, x; i < n; i++) scanf("%d", &x), a.pb(x);
a = Poly::Ksm(a, b);
for(int i = 0; i < n; i++) printf("%d ", a[i]); puts("");
return 0;
}
|