QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463395#6349. Is This FFT?atgcRE 61ms7456kbC++141.8kb2024-07-04 19:50:192024-07-04 19:50:19

Judging History

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

  • [2024-07-04 19:50:19]
  • 评测
  • 测评结果:RE
  • 用时:61ms
  • 内存:7456kb
  • [2024-07-04 19:50:19]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define d(i) ((i)*(i-1) >> 1)
using namespace std;
const int N = 201;
const int maxn = N*(N-1)>>1;
int n,mod,G;
int qpow(int a,int n){int ans=1;while(n){if(n&1)(ans*=a)%=mod;(a*=a)%=mod,n>>=1;}return ans;}
int inv[maxn],fac[maxn],ifac[maxn];
void init(){
	fac[0]=ifac[0]=inv[1]=fac[1]=ifac[1]=1;
	for(int i=2;i<maxn;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod,fac[i]=fac[i-1]*i%mod,ifac[i]=ifac[i-1]*inv[i]%mod;
}
int calG() {
	vector<int>ps;
	int x=mod-1;//assert(__builtin_ctz(x) >= 17);
	ps.push_back(2);x>>=__builtin_ctz(x);
	for(int i=3;i*i<=x;++i)if(x%i==0){ps.push_back(i);while(x%i==0)x/=i;}
	if(x!=1)ps.push_back(x);
	for(int G=2;;++G){
		for(int p:ps)
			if(qpow(G, (mod-1)/p) == 1) goto nxt;
		return G;nxt:;
	}
}
//cnt P that len=[j], pts = [i].

int rv[1<<15];
int f[1<<15], g[N][1<<15];
void NTT(int*a,int n){
	for(int i=1;i<n;++i)if(i<(rv[i]=(rv[i>>1]|(i&1)*n)>>1))swap(a[i],a[rv[i]]);
	for(int L=1;L<n;L<<=1)for(int i=0,wn=qpow(G,(mod-1)/L>>1);i<n;i+=L<<1)
		for(int j=0,w=1,u,v;j<L;++j,(w*=wn)%=mod)
			u=a[i|j],v=a[i|L|j],a[i|j]=(u+w*v)%mod,a[i|L|j]=(u-w*v)%mod;
}
void INTT(int*a,int n){NTT(a,n);reverse(a+1,a+n);for(int i=0,iv=qpow(n,mod-2);i<n;++i)(a[i]*=iv)%=mod;}


signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>mod;init();G=calG();int N=1<<15;

	inv[0]=1;g[1][0]=1;NTT(g[1],N);
	for(int i=2;i<=n;++i) {
		memset(f,0,sizeof f);
		for(int li=1;li<=i-li;++li)
			for(int j=0;j<N;++j)
				(f[j] += g[li][j]*g[i-li][j] << ((li<<1)!=i) ) %= mod;
		INTT(f,N);

		memmove(f+1,f,d(i) * sizeof f[0]);
		f[i-2]=0;

		for(int j=i-1;j<=d(i);++j) {
			(f[j] += f[j-1]*(d(i)-j+1)%mod*inv[j-1]) %= mod,
			g[i][j] = f[j]*inv[j]%mod;
		}

		NTT(g[i],N);

		cout<<(f[d(i)]*inv[d(i)]%mod*fac[i]%mod*inv[2]%mod+mod)%mod<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 61ms
memory: 7456kb

input:

10 998244353

output:

1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

ok 9 numbers

Test #2:

score: -100
Runtime Error

input:

250 998244353

output:


result: