为什么我好端端的代码本机会突然 RE
  • 板块灌水区
  • 楼主denominator
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/19 20:28
  • 上次更新2023/11/3 02:35:37
查看原帖
为什么我好端端的代码本机会突然 RE
174009
denominator楼主2023/8/19 20:28

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 均能正常运行,虽然结果不太正常。

2023/8/19 20:28
加载中...