已知多项式 ln 能过板子,然后我看了半天也没看出这个 exp 函数哪里写挂了。
于是调不出来,破防了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[4000005], b[4000005], tmp[4000005], tmp3[4000005], tmp2[4000005], fac[4000005], Inv[4000005], tmp4[4000005];
int n, m, l, r[4000005], p;
int lim = 1;
string aa, bb;
const int mod = 998244353;
int qpow(int x, int k){
int ans = 1;
while (k){
if (k & 1)
ans = ans * x % mod;
x = x * x % mod;
k >>= 1;
}
return ans;
}
void NTT(int *aa, int tp) {
for (int i = 0; i < lim; i++)
if (i < r[i])
swap(aa[i], aa[r[i]]);
for (int mid = 2; mid <= lim; mid <<= 1) {
int omega = qpow(3, (mod - 1) / mid);
for (int rr = mid >> 1, j = 0; j < lim; j += mid) {
int omega2 = 1;
for (int k = 0; k < rr; k++) {
int xx = aa[j + k], yy = omega2 * aa[j + k + rr] % mod;
aa[j + k] = (xx + yy) % mod;
aa[j + k + rr] = (xx - yy + mod) % mod;
omega2 = omega2 * omega % mod;
}
}
}
if (tp == -1){
reverse(aa + 1, aa + lim);
int inv = qpow(lim, mod - 2);
for (int i = 0; i < lim; i++)
aa[i] = aa[i] * inv % mod;
}
}
void polyInv(int *a, int *b, int n){
if (n == 1){
b[0] = qpow(a[0], mod - 2) % mod;
return;
}
polyInv(a, b, (n + 1) >> 1);
lim = 1, l = 0;
while (lim < (n << 1))
lim <<= 1, l++;
for (int i = 0; i < lim; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
for (int i = 0; i < n; i++)
tmp[i] = a[i];
for (int i = n; i < lim; i++)
tmp[i] = 0;
NTT(tmp, 1);
NTT(b, 1);
for (int i = 0; i < lim; i++)
b[i] = ((2 - b[i] * tmp[i]) % mod + mod) % mod * b[i] % mod;
NTT(b, -1);
for (int i = n; i < lim; i++)
b[i] = 0;
}
void der(int *a, int *tar, int n){
tar[n - 1] = 0;
for (int i = 1; i < n; i++)
tar[i - 1] = a[i] * i % mod;
}
void ining(int *a, int *tar, int n){
tar[0] = 0;
for (int i = 1; i < n; i++)
tar[i] = a[i - 1] * qpow(i, mod - 2) % mod;
}
void gln(int *a, int *b, int n){
der(a, tmp3, n);
polyInv(a, tmp2, n);
lim = 1, l = 0;
while (lim <= n)
lim <<= 1, l++;
for (int i = 0; i < lim; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
NTT(tmp3, 1);
NTT(tmp2, 1);
for (int i = 0; i < lim; i++)
tmp3[i] = tmp3[i] * tmp2[i] % mod;
NTT(tmp3, -1);
ining(tmp3, b, n);
}
void polyln(int *a, int *b, int n){
int LIM = 1;
while (LIM <= n)
LIM <<= 1;
gln(a, b, LIM);
}
void polyexp(int *a, int *b, int n){
if (n == 1){
b[0] = 1;
return;
}
polyexp(a, b, (n + 1) >> 1);
polyln(b, tmp4, n);
lim = 1, l = 0;
while (lim < (n << 1))
lim <<= 1, l++;
for (int i = 0; i < lim; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
for (int i = 0; i < n; i++)
tmp4[i] = ((a[i] - tmp4[i]) % mod + mod) % mod;
tmp4[0]++;
for (int i = n; i < lim; i++)
tmp4[i] = b[i] = 0;
NTT(tmp4, 1);
NTT(b, 1);
for (int i = 0; i < lim; i++)
b[i] = b[i] * tmp4[i] % mod;
NTT(b, -1);
for (int i = n; i < lim; i++)
b[i] = 0;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
polyexp(a, b, n);
for (int i = 0; i < n; i++)
cout << b[i] << " ";
return 0;
}