QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463261#6349. Is This FFT?bear0131WA 27ms11596kbC++144.5kb2024-07-04 16:42:042024-07-04 16:42:04

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 16:42:04]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:11596kb
  • [2024-07-04 16:42:04]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
struct BarrettModulo{
	ll p;
	__int128 q;
	void init(int Mod){
		p = Mod, q = ((__int128)1 << 64) / Mod;
	}
	ll mod(ll x){
		ll ret = (x - ((ll)(((__int128)x * q) >> 64) * p));
		(ret >= p) ? (ret -= p) : ret;
		return ret;
	}
} barrett;
int Mod, g_g;
inline void uadd(int &a, const int &b){ a += b - Mod; a += (a>>31) & Mod; }
inline int add(int a, const int &b){ a += b - Mod; a += (a>>31) & Mod; return a; }
inline void usub(int &a, const int &b){ a -= b; a += (a>>31) & Mod; }
inline int sub(int a, const int &b){ a -= b, a += (a>>31) & Mod; return a; }
inline void umul(int &a, const int &b){ a = (int)barrett.mod(1ll * a * b); }
inline int mul(const int &a, const int &b){ return (int)barrett.mod(1ll * a * b); }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 33333;
int fact[fN], invfact[fN], inv[fN];
void initfact(int n){
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i - 1], i);
	invfact[n] = qpow(fact[n], Mod - 2); for(int i = n; i > 0; --i) invfact[i - 1] = mul(invfact[i], i);
	for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i - 1]);
}
inline int binom(int n, int m){ return mul(fact[n], mul(invfact[m], invfact[n - m])); }

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template<typename T> inline void chmax(T &_a, const T &_b){ (_b>_a) ? (_a=_b) : _a; }
template<typename T> inline void chmin(T &_a, const T &_b){ (_b<_a) ? (_a=_b) : _a; }

namespace poly{
	int N, bl = -1;
	int w[1111111], to[1111111];
	void initN(int _n){
		int nbl = 0;
		while(1<<nbl < _n) ++nbl;
		if(nbl == bl) return ;
		bl = nbl, N = 1 << bl;
		rep(i, N) to[i] = (to[i >> 1] >> 1) | ((i & 1) << (bl - 1));
		w[0] = 1, w[1] = qpow(g_g, (Mod - 1) / N);
		for(int i = 2; i <= N; ++i) w[i] = mul(w[i - 1], w[1]);
	}
	void dft(vi &a, int idft = 0){
		a.resize(N);
		rep(i, N) if(to[i] < i) swap(a[i], a[to[i]]);
		for(int len = 0; len < bl; ++len) for(int l = 0; l < N; l += (1<<(len+1))){
			for(int i = 0; i < (1<<len); ++i){
				int x = a[l + i], y = mul(a[l + (1<<len) + i], w[i << (bl-len-1)]);
				a[l + i] = add(x, y), a[l + (1<<len) + i] = sub(x, y);
			}
		}
		if(idft){
			for(int i = 1; i < N - i; ++i) swap(a[i], a[N - i]);
			int invn = qpow(N, Mod - 2);
			rep(i, N) umul(a[i], invn);
		}
	}
	vi conv(vi a, vi b){
		initN((int)a.size() + (int)b.size() - 1);
		dft(a), dft(b);
		rep(i, N) umul(a[i], b[i]);
		dft(a, 1);
		while(a.back() == 0) a.pop_back();
		return a;
	}
}

int n;
int C2[222];
int sum[222][22222];
vi g[222];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> Mod;
	barrett.init(Mod);
	initfact(22222);

	{
		vi fac;
		int t = Mod - 1;
		for(int x = 2; x * x <= t; ++x) if(t % x == 0){
			fac.push_back(x);
			while(t % x == 0) t /= x;
		}
		if(t > 1) fac.push_back(t);
		for(g_g = 2; ; ++g_g){
			bool ok = 1;
			rep(i, (int)fac.size()){
				if(qpow(g_g, (Mod - 1) / fac[i]) % Mod == 1){ ok = 0; break; }
			}
			if(ok) break;
		}
	}

	//{
	//	int A, B;
	//	cin >> A >> B;
	//	vi a(A+1), b(B+1);
	//	rep(i, A+1) cin >> a[i];
	//	rep(i, B+1) cin >> b[i];
	//	a = poly::conv(a, b);
	//	rep(i, A+B+1) cout << a[i] << " ";
	//	cout << endl;
	//	return 0;
	//}

	rep(i, n+1) C2[i] = (i * (i-1)) / 2;
	poly::initN(32768);

	sum[1][0] = 1;
	g[1].push_back(1);
	poly::dft(g[1]);
	cout << "1\n";

	for(int i = 2; i <= n; ++i){
		vector<__int128> tmp(poly::N, 0);
		for(int a = 1; a < i-a; ++a){
			int b = i-a;
			rep(x, poly::N) tmp[x] += ((__int128)g[a][x]) * g[b][x];
		}
		rep(j, poly::N) tmp[j] *= 2;
		if(i % 2 == 0){
			int a = i/2;
			rep(x, poly::N) tmp[x] += ((__int128)g[a][x]) * g[a][x];
		}
		vi f(poly::N);
		rep(j, poly::N) f[j] = (int)(tmp[j] % Mod);
		poly::dft(f, 1);
		//rep(j, 8) cout << (int)f[j] << " ";
		//cout << "\n";
		for(int c = 0; c <= C2[i]; ++c){
			umul(f[c], fact[c]), umul(f[c], fact[C2[i] - c - 1]);
			sum[i][c + 1] = add(sum[i][c], f[c]);
		}
		int all = sum[i][C2[i] + 1];
		//cout << i << ": " << all << endl;
		cout << mul(mul(all, mul(fact[i], inv[2])), invfact[C2[i]]) % Mod << "\n";
		g[i].resize(poly::N);
		rep(c, C2[i] + 1){
			g[i][c] = sum[i][c];
			umul(g[i][c], invfact[c]);
			umul(g[i][c], invfact[C2[i] - c]);
		}
		poly::dft(g[i]);
	}

	cerr << 1. * clock() / CLOCKS_PER_SEC << endl;

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 27ms
memory: 11596kb

input:

10 998244353

output:

1
1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

wrong answer 3rd numbers differ - expected: '532396989', found: '1'