QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426050#6349. Is This FFT?ushg8877WA 3906ms172880kbC++143.0kb2024-05-30 20:41:012024-05-30 20:41:01

Judging History

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

  • [2024-05-30 20:41:01]
  • 评测
  • 测评结果:WA
  • 用时:3906ms
  • 内存:172880kb
  • [2024-05-30 20:41:01]
  • 提交

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){
	r=r-((r*m)>>64)*p;
	return (r>=p?r-p:r);
}
}using namespace FastMod;
namespace polynomial{// yjl poly plank 5.0 ver
const int MR=1e6+5;
int bfly[MR];
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(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: 7ms
memory: 8544kb

input:

10 998244353

output:

1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

ok 9 numbers

Test #2:

score: 0
Accepted
time: 3906ms
memory: 168844kb

input:

250 998244353

output:

1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062
289137877
768923227
177538883
440227465
101981224
874960215
35275208
664066979
334444870
46651494
799130693
122319095
913072242
44703442
965640306
52873544
461938281
263838691
777326453
356621754
560569747
812581766
46147702
12...

result:

ok 249 numbers

Test #3:

score: 0
Accepted
time: 3735ms
memory: 172880kb

input:

250 65537

output:

1
1
8739
5982
43573
63055
50957
48651
15842
40150
26535
53234
50550
8708
34485
48568
52730
2494
37477
52676
25640
62555
6175
28734
38834
6442
35198
41267
12029
47992
59673
56920
23395
6921
24280
30992
26117
42844
58258
60841
45860
45174
7890
61836
33308
31989
46003
26412
65049
3275
27651
24854
19324...

result:

ok 249 numbers

Test #4:

score: -100
Wrong Answer
time: 32ms
memory: 10300kb

input:

53 388104193

output:

1
1
103494452
258736129
366591373
316042954
8286743
165719455
76764487
79569391
119920409
248672172
70967921
288830028
372167317
246601528
217075355
30878703
257713757
195596822
74307888
28760556
40144420
152500056
256417368
179569968
233881251
14265023
139285509
52123153
223568602
85340031
38657339...

result:

wrong answer 3rd numbers differ - expected: '336356968', found: '103494452'