QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#463446#6349. Is This FFT?atgcRE 0ms0kbC++234.2kb2024-07-04 20:56:382024-07-04 20:56:39

Judging History

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

  • [2024-07-04 20:56:39]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-04 20:56:38]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


int n,m,mod,N,iN,d;

template <class ADD>
inline void add(ADD &x,ADD y){
	x += y;
	if(x >= mod) x -= mod;
}

template <class SUB>
inline void sub(SUB &x,SUB y){
	x -= y;
	if(x < 0) x += mod;
}
__int128 mu;
namespace barrett {
  	inline ll reduce(ll x) {
    	ll r = x - (mu * x >> 64) * mod;
    	return r >= mod ? r - mod : r;
  	}
  	inline void setmod(ll mod) {
    	mu = -1ull / mod;
  	}
}
using namespace barrett;
ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}
int lim[255];
ll dp[255][32005],val[255][65536],tmp[65536],fact[32005],ifac[32005],inv[32005];

int g;
int test(){
	if(power(g,(mod - 1) / 2) == 1) return 0;
	int cur = mod - 1;
	while(cur % 2 == 0) cur /= 2;
	for(int i = 2;i * i <= cur;i++){
		if(cur % i) continue;
		if(power(g,(mod - 1) / i) == 1) return 0;
		while(cur % i == 0) cur /= i;
	}
	return 1;
}
void init(){
	g = 1;
	while(!test()) g++;
//	printf("find g=%d\n",g);
}

ll ww[20][65536],iw[20][65536];
void reinit(){
	rep(i,0,d){
		ll w0 = power(g,(mod - 1) >> i);
		ww[i][0] = 1;
		rep(k,1,(1 << i) - 1) ww[i][k] = reduce(ww[i][k - 1] * w0);
		w0 = power(w0);
		iw[i][0] = 1;
		rep(k,1,(1 << i) - 1) iw[i][k] = reduce(iw[i][k - 1] * w0);
	}
}

void FFT(ll *f,int len,int op){
	if(len == 1) return;
	int hf = len / 2;
	rep(i,0,hf - 1){
		tmp[i] = f[2 * i];
		tmp[i + hf] = f[2 * i + 1];
	}
	rep(i,0,len - 1) f[i] = tmp[i];
	FFT(f,hf,op);FFT(f + hf,hf,op);
	ll qwq;
	int p = __lg(len);
	rep(i,0,hf - 1){
		tmp[i] = tmp[i + hf] = f[i];
		if(op == 1) qwq = reduce(f[i + hf] * ww[p][i]);
		else qwq = reduce(f[i + hf] * iw[p][i]);
		add(tmp[i],qwq);
		sub(tmp[i + hf],qwq);
	}
	rep(i,0,len - 1) f[i] = tmp[i];
}

void recalc(int i){
	rep(s,0,lim[i]) val[i][s] = reduce(dp[i][s] * ifac[s]);
	fill(val[i] + lim[i] + 1,val[i] + N,0);
	FFT(val[i],N,1);
}

int main(){
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
//	freopen("sub7_3.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d",&n,&mod);
	setmod(mod);
	m = n * (n - 1) / 2;
	N = iN = 1;
	init();
	reinit();
	
	fact[0] = 1;
	rep(i,1,m) fact[i] = fact[i - 1] * i % mod;
	ifac[m] = power(fact[m]);
	per(i,m - 1,0) ifac[i] = ifac[i + 1] * (i + 1) % mod;
//	rep(i,1,m) printf("%lld ",ifac[i]);
//	printf("\n");
	rep(i,1,m) inv[i] = ifac[i] * fact[i - 1] % mod;

	cerr << clock() << endl;
	rep(i,1,n) lim[i] = i * (i + 1) / 2;
	dp[0][0] = val[0][0] = 1;
	FFT(val[0],N,1);
	rep(i,1,n - 1){
		if(N <= lim[i]){
			while(N <= lim[i]){
				N *= 2;
				d++;
			}
			reinit();
			rep(j,0,i - 1) recalc(j);	
			iN = power(N);
		}
		rep(p,1,i){
			rep(k,0,N - 1) val[i][k] += val[p - 1][k] * val[i - p][k];
			if((p & 7) == 0) rep(k,0,N - 1) val[i][k] = reduce(val[i][k]);
		}
		rep(k,0,N - 1) val[i][k] = reduce(val[i][k]);
		FFT(val[i],N,-1);
		rep(s,0,lim[i]){
			dp[i][s + 1] = reduce(val[i][s] * fact[s]);
			dp[i][s + 1] = reduce(dp[i][s + 1] * iN);
		}
		rep(s,0,lim[i]) add(dp[i][s + 1],reduce(dp[i][s] * (lim[i] - s)));
		rep(s,0,lim[i]) val[i][s] = reduce(dp[i][s] * ifac[s]);
		FFT(val[i],N,1);
//		rep(s,0,m) printf("%lld ",dp[i][s]);
//		printf("\n");
	}
	ll i2 = power(2);
	rep(i,1,n - 1){
		ll output = reduce(dp[i][i * (i + 1) / 2] * fact[i + 1]);
		output = reduce(output * i2);
//		printf("%lld ",output);
		printf("%lld\n",reduce(output * ifac[i * (i + 1) / 2]));
	}
	cerr << clock() << endl;
	return 0;
}

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

10 998244353

output:


result: