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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
##define endl "\n"
const ll mod = 998244353;
const double PI = acos(-1);
const int N = 1e6 + 10;
struct Complex {
double x, y;
Complex(double a = 0, double b = 0): x(a), y(b) {}
Complex operator + (const Complex &rhs) { return Complex(x + rhs.x, y + rhs.y); }
Complex operator - (const Complex &rhs) { return Complex(x - rhs.x, y - rhs.y); }
Complex operator * (const Complex &rhs) { return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
Complex conj() { return Complex(x, -y); }
} w[N];
int tr[N];
ll f[N], g[N], invg[N], g2[N];
ll quick_pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
int getLen(int n) {
int len = 1; while (len < (n << 1)) len <<= 1;
for (int i = 0; i < len; i++) tr[i] = (tr[i >> 1] >> 1) (i & 1 ? len >> 1 : 0);
for (int i = 0; i < len; i++) w[i] = w[i] = Complex(cos(2 * PI * i / len), sin(2 * PI * i / len));
return len;
}
void FFT(Complex *A, int len) {
for (int i = 0; i < len; i++) if(i < tr[i]) swap(A[i], A[tr[i]]);
for (int i = 2, lyc = len >> 1; i <= len; i <<= 1, lyc >>= 1)
for (int j = 0; j < len; j += i) {
Complex *l = A + j, *r = A + j + (i >> 1), *p = w;
for (int k = 0; k < i >> 1; k++) {
Complex tmp = *r * *p;
*r = *l - tmp, *l = *l + tmp;
++l, ++r, p += lyc;
}
}
}
inline void MTT(ll *x, ll *y, ll *z, int n) {
int len = 1; while (len <= n) len <<= 1;
for (int i = 0; i < len; i++) tr[i] = (tr[i >> 1] >> 1) (i & 1 ? len >> 1 : 0);
for (int i = 0; i < len; i++) w[i] = w[i] = Complex(cos(2 * PI * i / len), sin(2 * PI * i / len));
for (int i = 0; i < len; i++) (x[i] += mod) %= mod, (y[i] += mod) %= mod;
static Complex a[N], b[N];
static Complex dfta[N], dftb[N], dftc[N], dftd[N];
for (int i = 0; i < len; i++) a[i] = Complex(x[i] & 32767, x[i] >> 15);
for (int i = 0; i < len; i++) b[i] = Complex(y[i] & 32767, y[i] >> 15);
FFT(a, len), FFT(b, len);
for (int i = 0; i < len; i++) {
int j = (len - i) & (len - 1);
static Complex da, db, dc, dd;
da = (a[i] + a[j].conj()) * Complex(0.5, 0);
db = (a[i] - a[j].conj()) * Complex(0, -0.5);
dc = (b[i] + b[j].conj()) * Complex(0.5, 0);
dd = (b[i] - b[j].conj()) * Complex(0, -0.5);
dfta[j] = da * dc;
dftb[j] = da * dd;
dftc[j] = db * dc;
dftd[j] = db * dd;
}
for (int i = 0; i < len; i++) a[i] = dfta[i] + dftb[i] * Complex(0, 1);
for (int i = 0; i < len; i++) b[i] = dftc[i] + dftd[i] * Complex(0, 1);
FFT(a, len), FFT(b, len);
for (int i = 0; i < len; i++) {
int da = (ll)(a[i].x / len + 0.5) % mod;
int db = (ll)(a[i].y / len + 0.5) % mod;
int dc = (ll)(b[i].x / len + 0.5) % mod;
int dd = (ll)(b[i].y / len + 0.5) % mod;
z[i] = (da + ((ll)(db + dc) << 15) + ((ll)dd << 30)) % mod;
}
}
void Get_Inv(ll *f, ll *g, int n) {
if(n == 1) { g[0] = quick_pow(f[0], mod - 2); return ; }
Get_Inv(f, g, (n + 1) >> 1);
int len = getLen(n);
static ll c[N];
for(int i = 0;i < len; i++) c[i] = i < n ? f[i] : 0;
MTT(c, g, c, len); MTT(c, g, c, len);
for(int i = 0;i < n; i++) g[i] = (2ll * g[i] - c[i] + mod) % mod;
for(int i = n;i < len; i++) g[i] = 0;
for(int i = 0;i < len; i++) c[i] = 0;
}
void init() {
g[0] = 1; for(int i = 1;i < 1e5 + 10; i++) g2[i] = g[i] = g[i - 1] * i % mod;
Get_Inv(g, invg, 1e5);
g[0] = g2[0] = 0;
MTT(g2, g, g2, 1e5 + 1e5);
MTT(g2, invg, f, 2e5 + 1e5);
}
void solve() {
init();
int _; cin >> _;
while(_--) {
int n; cin >> n;
cout << f[n] << endl;
}
}
signed main() {(cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
}
|