RT。Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 600010;
const ll mod = 998244353, g = 114514, invg = 137043501;
int n, m, rgt[N];
ll power (ll a, ll b, ll p) {
return b == 0? 1: (b & 1? a: 1) * power (a * a % p, b >> 1, p) % p;
}
void dft (vector <ll>& a, int inv) {
int n = a.size ();
assert ((n & (-n)) == n);
ll ninv = power (n, mod - 2, mod);
for (int i = 0; i < n; i++) {
if (i < rgt[i]) {
swap (a[i], a[rgt[i]]);
}
}
for (int mid = 1; mid < n; mid <<= 1) {
ll wn = power (inv == 1? g: invg, (mod - 1) / (mid << 1), mod);
for (int i = 0; i < n; i += mid << 1) {
ll w = 1;
for (int j = 0; j < mid; j++) {
ll x = a[i + j], y = w * a[i + j + mid] % mod;
a[i + j] = (x + y) % mod;
a[i + j + mid] = (x - y + mod) % mod;
(w *= wn) %= mod;
}
}
}
if (inv == -1) {
for (int i = 0; i < n; i++) {
(a[i] *= ninv) %= mod;
}
}
}
struct poly {
vector <ll> a;
poly () {}
poly (int n_) {
a.resize (n_ + 1);
}
poly& operator = (int n_) {
a.resize (n_ + 1);
return *this;
}
int size () {
return a.size () - 1;
}
ll& operator [] (int p) {
return a[p];
}
};
poly operator + (poly f, poly g) {
int n = max (f.size (), g.size ());
f = n;
g = n;
for (int i = 0; i <= n; i++) {
(f[i] += g[i]) %= mod;
}
return f;
}
poly operator - (poly f, poly g) {
int n = max (f.size (), g.size ());
f = n;
g = n;
for (int i = 0; i <= n; i++) {
((f[i] -= g[i]) += mod) %= mod;
}
return f;
}
poly operator * (poly f, poly g) {
int t = f.size () + g.size (), k = 0;
for (; (1 << k) <= t; k++);
f = (1 << k) - 1;
g = (1 << k) - 1;
dft (f.a, 1);
dft (g.a, 1);
for (int i = 0; i < (1 << k); i++) {
(f[i] *= g[i]) %= mod;
}
dft (f.a, -1);
return f = t;
}
poly inv (poly f, int n) {
poly f0 = 0, con = 0;
con[0] = 2;
f0[0] = power (f[0], mod - 2, mod);
int k = 0;
while ((1 << k) <= n + 1) {
f0 = f0 * (con - f0 * f);
f0 = (1 << (k + 1)) - 1;
k++;
}
return f0 = n;
}
poly a;
int main () {
scanf ("%d", &n);
int k = 0;
for (; (1 << k) <= (n << 2); k++);
for (int i = 0; i < (1 << k); i++) {
rgt[i] = (rgt[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
a = --n;
for (int i = 0; i <= n; i++) {
scanf ("%lld", &a[i]);
}
a = inv (a, n);
for (int i = 0; i <= n; i++) {
printf ("%lld%c", a[i], " \n"[i == n]);
}
return 0;
}
跳出 operator * 前还好端端的,return 前也好端端的,跳出 operator * 的一刹那就抛出 RE。
洛谷 & Hydro IDE 均能正常运行,虽然结果不太正常。