QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#463884#6349. Is This FFT?zyz07WA 0ms9724kbC++174.2kb2024-07-05 15:37:552024-07-05 15:37:55

Judging History

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

  • [2024-07-05 15:37:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9724kb
  • [2024-07-05 15:37:55]
  • 提交

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,typename=enable_if_t<is_integral_v<T>>>
T operator%(T x,const FastMod& Mod){
	return Mod.reduce(x);
}
template<typename T,typename=enable_if_t<is_integral_v<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)>>1;
}
namespace NTT{
	unsigned P;
	int G;
	const int N=1<<16;
	template<typename T>
	void mod(T& x){
		x=(x>=P?x-P:x);
	}
	unsigned long long W[N],IW[N];
	void init(int n){
		const int IG=power(G,P-2);
		for(int l=2,mid=1;l<=n;l<<=1,mid<<=1)
			for(int i=0,wn=power(G,(P-1)/l),iwn=power(IG,(P-1)/l),w=1,iw=1;i<mid;i++)
				W[mid+i]=w,IW[mid+i]=iw,w=((ll)w*wn)%P,iw=((ll)iw*iwn)%P;
	}
	void dft(unsigned long long* f,int n){
		unsigned long long x,y;
		for(int l=n,mid=l>>1;l>=2;l>>=1,mid>>=1)
			for(int p=0;p<n;p+=l){
				#pragma GCC unroll 16
				for(int i=0;i<mid;i++)
					x=f[p+i],y=f[p+mid+i],mod(f[p+i]+=y),f[p+mid+i]=W[mid+i]*(P+x-y)%Mod;
			}
	}
	void idft(unsigned long long* f,int n){
		unsigned long long x,y;
		for(int l=2,mid=1;l<=n;l<<=1,mid<<=1)
			for(int p=0;p<n;p+=l){
				#pragma GCC unroll 16
				for(int i=0;i<mid;i++)
					x=f[p+i],y=f[p+mid+i]*IW[mid+i]%Mod,mod(f[p+i]+=y),mod(f[p+i+mid]=P+x-y);
			}
		for(int i=0,invn=power(n,P-2);i<n;i++){
			f[i]=f[i]*invn%Mod;
		}
	}
	int gt(int l){
		int n=1;
		while(n<l)n<<=1;
		return n;
	}
}
const int N=255;
int n,mod;
ll f[N][N*N/2];
unsigned long long g[N*N],g_[N*N/2],a1[N*N],a2[N*N],dft[N][1<<15];
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;
}
void findrt(){
	int t=mod-1;
	vector<int> vs;
	for(int i=2;i<=t&&i*i<=mod;i++){
		if(t%i==0){
			vs.push_back(i);
			while(t%i==0) t/=i;
		}
	}
	if(t!=1) vs.push_back(t);
	for(int i=2;i<=mod;i++){
		bool flag=true;
		for(int j:vs){
			if(power(i,(mod-1)/j)==1){
				flag=false;
				break;
			}
		}
		if(flag)return NTT::G=i,void();
	}
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>mod;
	Mod=FastMod(mod);
	NTT::P=mod;
	findrt();
	NTT::init(1<<15);
	const int m=1<<14;
	init_fac();
	cout<<"1\n";
	f[0][0]=1;
	For(i,1,n){
		For(j,0,(i-1)/2){
			int cnt=(j+1)*(i-j)-1,l1=C2(j),l2=C2(i-1-j);
			if(min(l1,l2)>200){
				copy(range(dft[j]),a1);
				copy(range(dft[i-1-j]),a2);
				For(k,0,m-1){
					g[k]=a1[k]*a2[k]%Mod;
				}
				NTT::idft(g,m);
				int w=1+((i-1)%2||j<(i-1)/2);
				For(k,0,C2(j)+C2(i-1-j)){
					(f[i][k+cnt]+=g[k]*fac[C2(j+1)+C2(i-j)-k]*w)%=Mod;
				}
			}else{
				memset(g_,0,sizeof(g_));
				For(k,0,l1){
					a1[k]=f[j][k]*ifac[C2(j+1)-k]%Mod;
				}
				For(k,0,l2){
					a2[k]=f[i-1-j][k]*ifac[C2(i-j)-k]%Mod;
				}
				For(k1,0,l1){
					#pragma GCC unroll 16
					For(k2,0,l2){
						g_[k1+k2]+=a1[k1]*a2[k2];
					}
					if(k1==l1||!(k1&15)){
						#pragma GCC unroll 16
						For(k,0,l1+l2){
							g_[k]%=Mod;
						}
					}
				}
				int w=1+((i-1)%2||j<(i-1)/2);
				For(k,0,C2(j)+C2(i-1-j)){
					(f[i][k+cnt]+=g_[k]*fac[C2(j+1)+C2(i-j)-k]*w)%=Mod;
				}
			}
		}
		Dec(j,C2(i),0){
			f[i][j]=(f[i][j]*fac[j]+f[i][j+1])%Mod;
		}
		For(j,0,C2(i)){
			(f[i][j]*=ifac[j])%=Mod;
		}
		if(C2(i)>200){
			For(j,0,C2(i)){
				dft[i][j]=f[i][j]*ifac[C2(i+1)-j]%Mod;
			}
			NTT::dft(dft[i],m);
		}
	}
	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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9724kb

input:

10 998244353

output:

1
1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

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