QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426039#6349. Is This FFT?ushg8877WA 11729ms173764kbC++143.0kb2024-05-30 20:36:492024-05-30 20:36:50

Judging History

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

  • [2024-05-30 20:36:50]
  • 评测
  • 测评结果:WA
  • 用时:11729ms
  • 内存:173764kb
  • [2024-05-30 20:36:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define poly vector<long long>
const int MAXN=255;
ll MOD,k;
ll f[MAXN][MAXN*MAXN];
namespace FastMod{
ll m,p;
void init(ll pp){m=-1ull/pp,p=pp;}
ll Mod(LL r){
	return r%p;
	// return r-((r*m)>>64)*p;
}
}using namespace FastMod;
namespace polynomial{// yjl poly plank 5.0 ver
int bfly[MAXN];ll inver[MAXN];
int clogg(int x){return (int)ceil(log2(x));} 
ll ksm(ll a,int b){
	ll res=1;
	while(b){
		if(b&1)res=Mod(res*a);
		a=Mod(a*a),b>>=1;
	}
	return res;
}
void butterfly(int l){
	static int las;
	if(las!=l){
		las=l; 
		for(int i=1;i<(1<<l);i++)
			bfly[i]=(bfly[i>>1]>>1)|((i&1)<<(l-1));
	} 
}
void NTT(poly &f,int l,int typ){
	butterfly(l);f.resize(1<<l);
	for(int i=0;i<(1<<l);i++)
		if(bfly[i]<i) swap(f[i],f[bfly[i]]);
	for(int i=0;i<l;i++){
		ll step=ksm(3,MOD-1+((MOD-1)>>(i+1))*typ);
		for(int j=0;j<(1<<l);j+=(1<<(i+1))){
			ll cur=1,l=j+(1<<i);
			for(int k=j;k<l;k++){
				ll u=f[k],v=Mod(f[k|(1<<i)]*cur);
				f[k]=(u+v>MOD?u+v-MOD:u+v);
				f[k|(1<<i)]=(u>=v?u-v:u-v+MOD);
				cur=Mod(cur*step);
			}
		}
	}
	if(typ==-1){
		ll val=ksm(1<<l,MOD-2);
		for(int i=0;i<(1<<l);i++)
			f[i]=Mod(val*f[i]);
	}
	return;
}
poly operator *(poly f,poly g){
	while(!f.empty()&&f.back()==0) f.pop_back();
	while(!g.empty()&&g.back()==0) g.pop_back();
	if(f.empty()||g.empty()) return (poly){};
	int n=f.size()+g.size(),l=clogg(f.size()+g.size());
	if(n<=64){
		poly h(n-1);
		for(int i=0;i<(int)f.size();i++)
			for(int j=0;j<(int)g.size();j++)
				h[i+j]+=Mod(f[i]*g[j]);
		for(ll &i:h) i=Mod(i);
		return h;
	}
	NTT(f,l,1);NTT(g,l,1);
	for(int i=0;i<(1<<l);i++)
		f[i]=Mod(f[i]*g[i]);
	NTT(f,l,-1);f.resize(n-1);
	return f;
}
}using namespace polynomial;
ll fac[MAXN*MAXN],inf[MAXN*MAXN];
ll C(int n,int m){return n<0||n>m?0:inf[n]*inf[m-n]%MOD*fac[m]%MOD;}
poly F1[MAXN],F2[MAXN];
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	cin>>k>>MOD;
	int M=k*(k-1)/2+1;M=ceil(log2(M));
	init(MOD);
	fac[0]=inf[0]=1;
	for(int i=1;i<MAXN*MAXN;i++) inf[i]=ksm(fac[i]=Mod(fac[i-1]*i),MOD-2);
	f[1][0]=1;
	F1[1].resize(1<<M);F2[1].resize(1<<M);
	F1[1][0]=F2[1][0]=1;
	NTT(F1[1],M,0);NTT(F2[1],M,0);
	for(int n=2;n<=k;n++) {
		poly S(1<<M);
		for(int j=1;j<n;j++){
			for(int k=0;k<(1<<M);k++){
				S[k]+=Mod(F1[j][k]*F2[n-j][k]);
			}
		}
		for(auto &i:S) i=Mod(i);
		NTT(S,M,-1);
		for(int m=1;m<=n*(n-1)/2;m++){
			f[n][m]=Mod(Mod(Mod(S[m-1])*fac[n-1])*fac[m-1]);
			f[n][m]+=Mod(f[n][m-1]*(n*(n-1)/2-(m-1)));
			f[n][m]=Mod(f[n][m]);
		}
		cout<<Mod(f[n][n*(n-1)/2]*inf[n*(n-1)/2])<<'\n';
		F1[n].resize(1<<M),F2[n].resize(1<<M);
		for(int i=0;i<=n*(n-1)/2;i++){
			F1[n][i]=Mod(Mod(f[n][i]*inf[i])*inf[n-1]*2);
			F2[n][i]=Mod(Mod(f[n][i]*inf[i])*inf[n]*2);
		}
		NTT(F1[n],M,1);NTT(F2[n],M,1);
	}
	cerr<<"Running Time: "<<1.*clock()/CLOCKS_PER_SEC<<'\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 15ms
memory: 5016kb

input:

10 998244353

output:

1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

ok 9 numbers

Test #2:

score: -100
Wrong Answer
time: 11729ms
memory: 173764kb

input:

250 998244353

output:

59642706040768
-18651707589248
17894023300864
-45337559475328
39102308466752
6852223264064
-53646317811328
40969150795264
49590366252736
-27958285461952
-16640585857024
1079388391808
-52215243837952
55027609783488
10098033064512
-70517367761600
40428383822016
-33830282663232
27500886192128
-38676816...

result:

wrong answer 1st numbers differ - expected: '1', found: '59642706040768'