#include <cstring>
#include <iostream>
#include <random>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 2e6;
const int_t mod = 998244353;
const int_t g = 3;
int_t power(int_t b, int_t i) {
int_t r = 1;
if (i < 0)
i = (i % (mod - 1) + mod - 1) % (mod - 1);
while (i) {
if (i & 1)
r = r * b % mod;
b = b * b % mod;
i >>= 1;
}
return r;
}
void makeflip(int_t* arr, int_t size2) {
int_t len = (1 << size2);
arr[0] = 0;
for (int_t i = 1; i < len; i++) {
arr[i] = (arr[i >> 1] >> 1) | ((i & 1) << (size2 - 1));
}
}
int_t upper2n(int_t x) {
int_t r = 0;
while ((1 << r) < x)
r++;
return r;
}
template <int_t arg = 1>
void transform(int_t* A, int_t size2, int_t* flip) {
int_t len = (1 << size2);
for (int_t i = 0; i < len; i++) {
int_t r = flip[i];
if (r > i)
std::swap(A[i], A[r]);
}
for (int_t i = 2; i <= len; i *= 2) {
int_t mr = power(g, arg * (mod - 1) / i);
for (int_t j = 0; j < len; j += i) {
int_t curr = 1;
for (int_t k = 0; k < i / 2; k++) {
int_t u = A[j + k], v = curr * A[j + k + i / 2] % mod;
A[j + k] = (u + v) % mod;
A[j + k + i / 2] = (u - v + mod) % mod;
curr = curr * mr % mod;
}
}
}
}
void poly_inv(const int_t* A, int_t n, int_t* result) {
/*
这里的n是模x^n
计算B(x)*A(x) = 1 mod x^n, 其中A(x)已知
假设已知A(x)*B(x) = 1 mod x^{ceil(n/2)}
假设C(x)*A(x) = 1 mod x^n
(A(x)B(x)-1)^2 = A^2(x)B^2(x)-2A(x)B(x)+1= 0
A(x)B^2(x)-2B(x)+C(x) = 0
C(x) = 2B(x)-A(x)B^2(x)
*/
// #ifdef DEBUG
// cout << "at " << n << endl;
// #endif
if (n == 1) {
result[0] = power(A[0], -1);
return;
}
int_t next = n / 2 + n % 2;
poly_inv(A, next, result);
//次数不要选错了，应该用n次的A和B去卷
int_t size2 = upper2n(n + 2 * next + 1);
static int_t X[LARGE];
static int_t Y[LARGE];
int_t len = (1 << size2);
// 写错设置范围了！
memset(X + n, 0, sizeof(X[0]) * (len - n));
memset(Y + next, 0, sizeof(Y[0]) * (len - next));
memcpy(X, A, sizeof(A[0]) * n);
memcpy(Y, result, sizeof(result[0]) * next);
static int_t fliparr[LARGE];
makeflip(fliparr, size2);
transform<1>(X, size2, fliparr);
transform<1>(Y, size2, fliparr);
for (int_t i = 0; i < len; i++) {
X[i] = (2 * Y[i] - X[i] * Y[i] % mod * Y[i] % mod + mod) % mod;
}
transform<-1>(X, size2, fliparr);
const int_t inv = power(len, -1);
for (int_t i = 0; i < n; i++)
result[i] = X[i] * inv % mod;
#ifdef DEBUG
cout << "poly inv at " << n << endl;
cout << "result = ";
for (int_t i = 0; i < next; i++)
cout << result[i] << " ";
cout << endl;
#endif
}
int_t poly_divat(const int_t* F, const int_t* G, int_t n, int_t k) {
/*
n次多项式F和G
计算F(x)/G(x)的k次项前系数
考虑F(x)*G(-x)/G(x)*G(-x)，分母只有偶数次项，写为C(x^2)；分子写成xA(x^2)+B(x^2)，如果k是奇数，那么递归(A,C,n,k/2)，如果k是偶数，那么递归(B,C,n,k/2)
到k<=n时直接计算
*/
int_t size2 = upper2n(2 * n + 1);
int_t len = 1 << size2;
static int_t fliparr[LARGE];
makeflip(fliparr, size2);
static int_t T1[LARGE], T2[LARGE], T3[LARGE];
for (int_t i = 0; i < len; i++) {
if (i <= n)
T1[i] = F[i], T2[i] = G[i];
else
T1[i] = T2[i] = T3[i] = 0;
}
const int_t inv = power(len, -1);
while (k >= n) {
#ifdef DEBUG
cout << "curr at k = " << k << endl;
#endif
for (int_t i = 0; i < len; i++) {
if (i <= n) {
T3[i] = T2[i] * (i % 2 ? (mod - 1) : 1);
} else
T3[i] = 0;
}
transform(T1, size2, fliparr);
transform(T2, size2, fliparr);
transform(T3, size2, fliparr);
for (int_t i = 0; i < len; i++) {
T1[i] = T1[i] * T3[i] % mod;
T2[i] = T2[i] * T3[i] % mod;
}
transform<-1>(T1, size2, fliparr);
transform<-1>(T2, size2, fliparr);
#ifdef DEBUG
cout << "prod T1 = ";
for (int_t i = 0; i < len; i++)
cout << T1[i] * inv % mod << " ";
cout << endl;
cout << "prod T2 = ";
for (int_t i = 0; i < len; i++)
cout << T2[i] * inv % mod << " ";
cout << endl;
#endif
for (int_t i = 0; i < len; i++) {
if (i * 2 < len) {
T2[i] = T2[i * 2] * inv % mod;
} else
T2[i] = 0;
}
int_t b = k % 2;
for (int_t i = 0; i < len; i++) {
if (i % 2 == b) {
T1[i / 2] = T1[i] * inv % mod;
#ifdef DEBUG
cout << "at " << i << " assgin " << T1[i] * inv << " to "
<< i / 2 << endl;
#endif
}
#ifdef DEBUG
cout << "assign 0 to " << i << endl;
#endif
if (i > 0)
T1[i] = 0;
}
#ifdef DEBUG
cout << "finished T1 = ";
for (int_t i = 0; i < len; i++)
cout << T1[i] % mod << " ";
cout << endl;
cout << "finished T2 = ";
for (int_t i = 0; i < len; i++)
cout << T2[i] % mod << " ";
cout << endl;
#endif
k >>= 1;
}
poly_inv(T2, k + 1, T3);
// #ifdef DEBUG
// cout << "finished k = " << k << endl;
// cout << "T1 = ";
// for (int_t i = 0; i < len; i++)
// cout << T1[i] % mod << " ";
// cout << endl;
// cout << "T2 = ";
// for (int_t i = 0; i < len; i++)
// cout << T2[i] % mod << " ";
// cout << endl;
// cout << "T2 inv = ";
// for (int_t i = 0; i < len; i++)
// cout << T3[i] % mod << " ";
// cout << endl;
// #endif
int_t result = 0;
//计算结果的k次项
for (int_t i = 0; i <= k; i++) {
result = (result + T1[i] * T3[k - i] % mod) % mod;
}
return result;
}
void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {
/*
计算n次多项式A与m次多项式B的乘积
*/
int_t size2 = upper2n(n + m + 1);
int_t len = 1 << size2;
static int_t T1[LARGE], T2[LARGE];
for (int_t i = 0; i < len; i++) {
if (i <= n)
T1[i] = A[i];
else
T1[i] = 0;
if (i <= m)
T2[i] = B[i];
else
T2[i] = 0;
}
static int_t fliparr[LARGE];
makeflip(fliparr, size2);
transform(T1, size2, fliparr);
transform(T2, size2, fliparr);
for (int_t i = 0; i < len; i++)
T1[i] = T1[i] * T2[i] % mod;
transform<-1>(T1, size2, fliparr);
int_t inv = power(len, -1);
for (int_t i = 0; i <= n + m; i++)
C[i] = T1[i] * inv % mod;
}
int_t poly_linear_rec(const int_t* A0, const int_t* F0, int_t n, int_t k) {
/*
计算线性递推
F[1],F[2]...F[k] 递推系数
A[0],A[1]...A[k-1] 首项
A[m]=A[m-1]*F[1]+A[m-2]*F[2]+...+A[m-k]*F[k]
*/
static int_t T1[LARGE], T2[LARGE];
static int_t Ax[LARGE], Fx[LARGE];
Fx[0] = 0;
Ax[k] = 0;
for (int i = 1; i <= k; i++) {
Fx[i] = F0[i];
Ax[i - 1] = A0[i - 1];
}
poly_mul(Ax, k, Fx, k, T1);
T1[0] = Ax[0];
for (int i = 1; i <= k - 1; i++) {
T1[i] = (Ax[i] - T1[i] + mod) % mod;
}
for (int i = k; i <= 2 * k; i++)
T1[i] = 0;
T2[0] = 1;
for (int i = 1; i <= k; i++)
T2[i] = (mod - Fx[i]) % mod;
// #ifdef DEBUG
// cout << "T1 = ";
// for (int_t i = 0; i <= k; i++) {
// cout << T1[i] << " ";
// }
// cout << endl;
// cout << "T2 = ";
// for (int_t i = 0; i <= k; i++) {
// cout << T2[i] << " ";
// }
// cout << endl;
// #endif
return poly_divat(T1, T2, k, n);
}
void poly_log(const int_t* A, int_t n, int_t* out) {
/*
计算log(A(x)), A(x)为n次多项式
DlogF(x) =DF(x)/F(x)
*/
static int_t Ad[LARGE];
static int_t Finv[LARGE];
static int_t R[LARGE];
const int_t m = n - 1;
for (int_t i = 0; i <= m; i++) {
Ad[i] = A[i + 1] * (i + 1) % mod;
}
Ad[n] = 0;
poly_inv(A, n + 1, Finv);
poly_mul(Ad, m, Finv, n, R);
for (int_t i = 1; i <= n; i++) {
out[i] = R[i - 1] * power(i, -1) % mod;
}
}
void poly_exp(const int_t* A, int_t n, int_t* out) {
/*
计算exp(A(x)), A(x)为n次多项式
H(x)=G(x)(1-logG(x)+A(x))
H(x)为当次递推项，G(x)为上一次递推项
*/
if (n == 1) {
out[0] = 1;
return;
}
int_t r = n / 2 + n % 2;
poly_exp(A, r, out);
static int_t G[LARGE];
static int_t G2[LARGE];
static int_t logG[LARGE];
static int_t R[LARGE];
for (int_t i = 0; i < r; i++)
G[i] = out[i];
for (int_t i = r; i < n; i++)
G[i] = 0;
poly_log(G, n - 1, logG);
// for (int_t i = r; i < n; i++)
// logG[i] = 0;
for (int_t i = 0; i < n; i++) {
G2[i] = (mod - logG[i] + A[i]) % mod;
}
G2[0] = (G2[0] + 1) % mod;
poly_mul(G, n - 1, G2, n - 1, R);
for (int_t i = 0; i < n; i++)
out[i] = R[i];
#ifdef DEBUG
cout << "at " << n << endl;
cout << "A = ";
for (int_t i = 0; i < n; i++)
cout << A[i] << " ";
cout << endl;
cout << "G = ";
for (int_t i = 0; i < n; i++)
cout << G[i] << " ";
cout << endl;
cout << "logG = ";
for (int_t i = 0; i < n; i++)
cout << logG[i] << " ";
cout << endl;
cout << "G2 = ";
for (int_t i = 0; i < n; i++)
cout << G2[i] << " ";
cout << endl;
cout << "R = ";
for (int_t i = 0; i < n; i++)
cout << R[i] << " ";
cout << endl;
cout << endl;
#endif
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int_t n;
cin >> n;
static int_t A[LARGE], B[LARGE];
static int_t C[LARGE];
for (int_t i = 0; i < n; i++)
cin >> A[i];
poly_exp(A, n, B);
for (int_t i = 0; i < n; i++)
cout << B[i] << " ";
return 0;
}
发表回复