QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153699#6349. Is This FFT?PhantomThreshold#TL 3ms12864kbC++205.4kb2023-08-30 19:12:312023-08-30 19:12:31

Judging History

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

  • [2023-08-30 19:12:31]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:12864kb
  • [2023-08-30 19:12:31]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
struct Barrett {
	u64 b, m;
	Barrett() : b(), m() {}
	Barrett(u64 _b) : b(_b), m(-1ULL / _b) {}
	u32 reduce(u64 x) {
		u64 q = (u64)((u128(m) * x) >> 64), r = x - q * b;
		return r - b * (r >= b);
	}
} BA;

u32 mult(u32 x, u32 y) {
	return BA.reduce((u64)x * y);
}

const int maxn = 255;
const int maxm = (1<<16)+5;

int P;
inline void add(int &a,const int &b){ a+=b; if(a>=P) a-=P; }
int pw(int x,int k)
{
	int re=1;
	for(;k;k>>=1,x=mult(x,x)) if(k&1)
		re=mult(re,x);
	return re;
}
int invi(int x){ return pw(x,P-2); }
int fac[maxm],ifac[maxm];
int C(int i,int j)
{
	if(i<0||j<0||i<j) return 0;
	return mult(fac[i],mult(ifac[j],ifac[i-j]));
}
int findg()
{
	vector<int>pi;
	int tmpP = P-1;
	for(int i=2;i*i<=tmpP;i++) if(tmpP%i==0)
	{
		pi.push_back(i);
		while(tmpP%i==0) tmpP/=i;
	}
	if(tmpP>1) pi.push_back(tmpP);
	for(int i=2;;i++)
	{
		int ok=1;
		for(auto k:pi) if( pw(i,(P-1)/k)==1 )
		{
			ok=0;
			break;
		}
		if(ok) return i;
	}
}

int g,gi[maxm];
void pre()
{
	fac[0]=1; for(int i=1;i<maxm;i++) fac[i]=mult(fac[i-1],i);
	ifac[maxm-1]=invi(fac[maxm-1]);
	for(int i=maxm-2;i>=0;i--) ifac[i]=mult(ifac[i+1],i+1);
	
	gi[0]=1; gi[1]=pw(g,(P-1)/(1<<16));
	for(int i=2;i<=(1<<16);i++) gi[i]=mult(gi[i-1],gi[1]);
}

int id[maxm],N,ln;
void DFT(int f[],const int sig)
{
	for(int i=1;i<N;i++) if(i<id[i]) swap(f[i],f[id[i]]);
	
	for(int m=2;m<=N;m<<=1)
	{
		int t=m>>1,tt=(1<<16)/m;
		int wn= gi[ sig==1?tt:(1<<16)-tt ];
		for(int j=0;j<N;j+=m)
		{
			int ww=1;
			for(int i=0;i<t;i++)
			{
				int tx=f[j+i], ty=mult(f[j+i+t],ww);
				f[j+i]= (tx+ty); 
				if(f[j+i]>=P) f[j+i]-=P;
				f[j+i+t]= (tx-ty); 
				if(f[j+i+t]<0) f[j+i+t]+=P;
				ww= mult(ww,wn);
			}
		}
	}
	
	if(sig==-1)
	{
		int iN= mult( ifac[N],fac[N-1] );
		for(int i=0;i<N;i++) f[i]=mult(f[i],iN);
	}
}

int n;
int e[maxn];
int f[maxn][maxm];
int a[maxn][maxm],b[maxn][maxm],c[maxm],ret[maxm];


signed main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> P;
	BA = Barrett(P);
	g = findg();
	
	pre();
	for(int i=1;i<=n;i++) e[i]=i*(i-1)/2;
	
	N=1,ln=0;
	f[0][0]=1;
	f[1][0]=1;
	f[2][1]=1;
	for(int i=3;i<=n;i++)
	{
		int flag=0;
		if(N<=e[i])
		{
			flag=1;
			while(N<=e[i]) N<<=1,ln++;
		}
		if(flag)
		{
			for(int s=1;s<N;s++) id[s]=id[s>>1]>>1|(s&1)<<(ln-1);
			for(int j=1;j<i;j++)
			{
				int sum=0;
				for(int x=0;x<=e[j];x++)
				{
					add(sum,f[j][x]);
					a[j][x]= mult( mult( mult( mult( sum, ifac[j] ), ifac[x] ), ifac[e[j]-x] ), 1+(j!=1) );
					if(x>0) b[j][x]= mult( mult( mult( mult( f[j][x], ifac[j] ), ifac[x-1] ), ifac[e[j]-x] ), 1+(j!=1) );
					else b[j][x]= 0;
				}
				for(int x=e[j]+1;x<N;x++) a[j][x]=b[j][x]=0;
				
		//		for(int x=0;x<2;x++) a[j][x]=1;
		//		for(int x=0;x<2;x++) b[j][x]=2;
				
				DFT(a[j],1);
				DFT(b[j],1);
				
		//		for(int x=0;x<N;x++) c[x]=mult(a[j][x],b[j][x]);
		//		DFT(c,-1);
			}
		}
		else
		{
			for(int j=i-1;j<i;j++)
			{
				int sum=0;
				for(int x=0;x<=e[j];x++)
				{
					add(sum,f[j][x]);
					a[j][x]= mult( mult( mult( mult( sum, ifac[j] ), ifac[x] ), ifac[e[j]-x] ), 1+(j!=1) );
					if(x>0) b[j][x]= mult( mult( mult( mult( f[j][x], ifac[j] ), ifac[x-1] ), ifac[e[j]-x] ), 1+(j!=1) );
					else b[j][x]= 0;
				}
				for(int x=e[j]+1;x<N;x++) a[j][x]=b[j][x]=0;
				
		//		for(int x=0;x<2;x++) a[j][x]=1;
		//		for(int x=0;x<2;x++) b[j][x]=2;
				
				DFT(a[j],1);
				DFT(b[j],1);
				
		//		for(int x=0;x<N;x++) c[x]=mult(a[j][x],b[j][x]);
		//		DFT(c,-1);
			}
		}
		
		for(int u=1;u<i;u++)
		{
			int v=i-u;
			
			for(int x=0;x<N;x++) ret[x]= mult( a[u][x], b[v][x] );
			DFT(ret, -1);
			
			ret[0]=0;
			for(int x=1;x<=e[u]+e[v];x++)
			{
				ret[x]= mult( mult( mult(ret[x],fac[u+v]), fac[x-1]), fac[e[u]+e[v]-x] );
			}
			
			int sum=0;
			for(int x=0;x+u*v-1<=e[i];x++)
			{
				add(f[i][x], mult( mult(sum,fac[e[i]-x]), ifac[e[i]-x-u*v+1]) );
				add(sum,ret[x]);
			}
		}
		
	//	cerr<<i<<" : "<<clock()<<endl;
	}
	/*
	
	1,0 + 2,1
	1*1 *6
	for(int i=3;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			// f j,x (+k)  *  f i-j,y
			for(int x=j-1;x<=e[j];x++)
			{
				for(int y=max(1,i-j-1);y<=e[i-j];y++)
				{
					for(int k=0;x+k<=e[j];k++)
					{
						u32 cc=
						mult( mult( mult( f[j][x],f[i-j][y] ), C(i,j) ) , mult( C(x+k+y-1,y-1) ,C(e[j]-x-k+e[i-j]-y,e[i-j]-y) ) );
						if(j!=1) cc=mult(cc,2);
						if(i-j!=1) cc=mult(cc,2);
						//x+k+y
						for(int x2=x+y+k+1;x2<=e[i];x2++)
						{
							add(f[i][x2], mult( mult(cc,C(e[i]-x2,j*(i-j)-1)),fac[j*(i-j)-1] ));
						}
					}
				}
			}
		}
	}
	*/
	/*
	
	f[i][x] (+k) 
	f[j][y]
	
	f[i][x]/i!/(x+k)!/(e[i]-x-k)!*(1+[i!=1])   *f[j][y]/j!/(y-1)!/(e[j]-y)!*(1+(j!=1)) 
	(i+j)! (x+k+y-1)! (e[i]+e[j]-x-y-k)!
	
	g[i+j][x+k+y]
	
	g[x]->g[y]
	
	x(+c)=y
	
	g[x]*C(E-y,e-1)*(e-1)!
	= g[x] * (E-y)! / (E-y-e+1)!
	
	
	*C(e[i+j]-x-y-k-c,i*j-1) *(i*j-1)!
	
	*/
	
	for(int i=2;i<=n;i++)
	{
		int ans=0;
		for(int j=i-1;j<=e[i];j++) add(ans,f[i][j]);
		//cout<<ans<<' ';
		cout<<mult( ans , ifac[e[i]] )<<endl;
	}
	
	return 0;
}


/*

10 998244353
1 1
6 1
528 532396989
1627200 328786831
165386946 443364983
584100363 567813846
223285012 34567523
931131059 466373946
157453919 474334062

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 12864kb

input:

10 998244353

output:

1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

ok 9 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

250 998244353

output:


result: