QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#450553#6349. Is This FFT?zyz07RE 0ms0kbC++172.3kb2024-06-22 15:26:432024-06-22 15:26:44

Judging History

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

  • [2024-06-22 15:26:44]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-06-22 15:26:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define range(Tx) begin(Tx),end(Tx)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using ll=long long;
struct FastMod{
	using ull=unsigned long long;
	using L=__int128;
	ull b,m;
	FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
	ull reduce(ull a) const{
		ull q=(ull)((L(m)*a)>>64),r=a-q*b;
		return r>=b?r-b:r;
	}
}Mod(2);
template<typename T>
T operator%(T x,const FastMod& Mod){
	return Mod.reduce(x);
}
template<typename T>
T& operator%=(T& x,const FastMod& Mod){
	return x=Mod.reduce(x);
}
ll power(ll x,ll y){
	ll r=1;
	for(;y;y>>=1,x=x*x%Mod){
		if(y&1) r=r*x%Mod;
	}
	return r;
}
int C2(int x){
	return x*(x-1)/2;
}
const int N=205;
int n,mod;
ll f[N][N*N/2],a1[N*N/2],a2[N*N/2];
__int128 g[N*N/2];
ll fac[N*N],inv[N*N],ifac[N*N];
void init_fac(){
	fac[0]=1;
	For(i,1,N*N-1) fac[i]=fac[i-1]*i%Mod;
	inv[1]=1;
	For(i,2,N*N-1) inv[i]=(mod-mod/i)*inv[mod%i]%Mod;
	ifac[0]=ifac[1]=1;
	For(i,2,N*N-1) ifac[i]=ifac[i-1]*inv[i]%Mod;
}
ll combine(int n,int m){
	return fac[n+m]*ifac[n]%Mod*ifac[m]%Mod;
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	assert(freopen("tree.in","r",stdin));
	assert(freopen("tree.out","w",stdout));
	cin>>n>>mod;
	Mod=FastMod(mod);
	init_fac();
	cout<<"1\n";
	f[0][0]=1;
	For(i,1,n){
		For(j,0,(i-1)/2){
			memset(g,0,sizeof(g));
			int cnt=(j+1)*(i-j)-1;
			For(k,0,C2(j)){
				a1[k]=f[j][k]*ifac[C2(j+1)-k]%Mod;
			}
			For(k,0,C2(i-1-j)){
				a2[k]=f[i-1-j][k]*ifac[C2(i-j)-k]%Mod;
			}
			int l1=C2(j),l2=C2(i-1-j);
			For(k1,0,l1){
				#pragma GCC unroll 16
				For(k2,0,l2){
					g[k1+k2]+=a1[k1]*a2[k2];
				}
			}
			if((i-1)%2||j<(i-1)/2){
				For(k,0,C2(j)+C2(i-1-j)){
					g[k]*=2;
				}
			}
			// vector<int> b=atcoder::convolution()
			For(k,0,C2(j)+C2(i-1-j)){
				(f[i][k+cnt]+=g[k]%mod*fac[k+cnt]%Mod*fac[C2(j+1)+C2(i-j)-k])%=Mod;
			}
		}
		Dec(j,C2(i),0){
			(f[i][j]+=f[i][j+1])%=Mod;
		}
		For(j,0,C2(i)){
			(f[i][j]*=ifac[j])%=Mod;
		}
	}
	For(i,1,n-1){
		ll ans=f[i][0],inv=2;
		For(j,1,i+1){
			(ans*=j)%=Mod;
		}
		For(j,1,i*(i+1)/2){
			(inv*=j)%=Mod;
		}
		cout<<ans*power(inv,mod-2)%Mod<<'\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

10 998244353

output:


result: