QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243645#7647. 树哈希AFewSuns77 3272ms10060kbC++143.8kb2023-11-08 15:24:202023-11-08 15:24:20

Judging History

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

  • [2023-11-08 15:24:20]
  • 评测
  • 测评结果:77
  • 用时:3272ms
  • 内存:10060kb
  • [2023-11-08 15:24:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
ll n,q,mod,pw[110],jc[110],jcinv[110],PW[110][110],C[110][110];
ll m=0,cnt[110],f[110],g[110],gg[110],ans[110];
ll A[110][110][110],B[110];
struct FastMod{
	#define ull unsigned long long
	ull n,m;
	il void init(ull p){
		n=p;
		m=((__int128)1<<64)/n;
	}
	il ll reduce(ull x){
		ull res=((__int128)x*m)>>64;
		res=x-res*n;
		return (res>=n)?(res-n):res;
	}
	#undef ull
}F;
il void inc(ll &x,ll y){
	((x+=y)>=mod)?(x-=mod):0;
}
il ll work(ll x){
	if(x==1) return F.reduce(PW[f[1]][f[1]-1]*F.reduce(pw[f[1]]*jcinv[f[x]]));
	fr(i,0,x) g[i]=0;
	g[0]=1;
	fr(p,1,x-1){
		if(!f[p]) continue;
		fr(i,0,x) gg[i]=g[i];
		fr(i,0,x) g[i]=0;
		fr(i,0,x) for(ll j=0;j<=i;j+=p) if(gg[i-j]) inc(g[i],F.reduce(gg[i-j]*A[p][f[p]][j]));
	}
	inc(g[0],mod-1);
	fr(i,0,x) g[i]=F.reduce(g[i]*q);
	fr(i,0,x) gg[i]=0;
	gg[0]=1;
	fr(i,0,x-1){
		gg[i]=F.reduce((i+1)*g[i+1]);
		fr(j,0,i-1) inc(gg[i],mod-F.reduce(gg[j]*g[i-j]));
	}
	ll sum=F.reduce(gg[x-1]*F.reduce(jc[x-1]*jcinv[x])),mul=1,res=0;
	fr(k,1,f[x]){
		mul=F.reduce(mul*sum);
		if(k==f[x]) inc(res,mul);
		else inc(res,F.reduce(mul*F.reduce(k*F.reduce(PW[f[x]][f[x]-k-1]*F.reduce(C[f[x]][k]*pw[f[x]-k])))));
	}
	return F.reduce(res*jcinv[f[x]]);
}
void dfs(ll lim,ll sum,ll res){
	if(cnt[m-1]!=cnt[m]&&m>1){
		ll x=cnt[m-1];
		res=F.reduce(res*work(x));
//		fr(i,0,n) g[i]=B[i];
//		fr(i,0,n) B[i]=0;
//		fr(i,0,n) for(ll j=0;j<=i;j+=x) inc(B[i],F.reduce(g[i-j]*A[x][f[x]][j]));
	}
	inc(ans[sum],F.reduce(res*work(cnt[m])));
	fr(i,lim,n-sum){
		cnt[++m]=i;
		f[i]++;
		dfs(i,sum+i,res);
		m--;
		f[i]--;
		if(!sum) break;
	}
//	if(cnt[m-1]!=cnt[m]&&m>1){
//		ll x=cnt[m-1];
//		fr(i,0,n) for(ll j=x;j<=i;j+=x) inc(B[i],mod-F.reduce(B[i-j]*A[x][f[x]][j]));
//	}
}
il void init(){
	pw[0]=jc[0]=1;
	fr(i,1,n) pw[i]=pw[i-1]*q%mod;
	fr(i,1,n) jc[i]=jc[i-1]*i%mod;
	jcinv[n]=inv(jc[n],mod);
	pfr(i,n-1,0) jcinv[i]=jcinv[i+1]*(i+1)%mod;
	fr(p,1,n){
		A[p][0][0]=1;
		fr(i,0,n/p) A[p][1][i]=my_pow(jcinv[i],p,mod);
		fr(i,2,n/p) fr(j,0,n/p) fr(k,0,j) inc(A[p][i][j],F.reduce(A[p][i-1][k]*A[p][1][j-k]));
		fr(i,1,n/p){
			pfr(j,n,0){
				if(j%p==0) A[p][i][j]=A[p][i][j/p];
				else A[p][i][j]=0;
			}
		}
	}
	fr(i,1,n){
		PW[i][0]=1;
		fr(j,1,n) PW[i][j]=F.reduce(PW[i][j-1]*i);
	}
	fr(i,0,n){
		C[i][0]=1;
		fr(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
}
int main(){
	n=read();
	q=read();
	mod=read();
	F.init(mod);
	ll N=n;
	n=min(n,57ll);
	init();
	B[0]=1;
	dfs(1,0,1);
	fr(i,1,n) writeln(F.reduce(ans[i]*jc[i-1]));
	fr(i,n+1,N) writeln(0);
}
/*
100 2 998244353
ans:
2
4
20
172
2052
*/

详细

Subtask #1:

score: 77
Acceptable Answer

Test #1:

score: 77
Acceptable Answer
time: 3272ms
memory: 7960kb

input:

100 910342260 935929297

output:

910342260
816177711
569226551
514707635
267406725
391906453
250727611
208481307
81485772
23235693
216730633
285646992
175230876
274553119
174038157
203318484
775234565
322891510
933522659
900692754
745314049
700055439
779013783
855717291
855228480
586396378
894281940
384312444
837857031
272136268
26...

result:

points 0.770 You got 77 pts!

Test #2:

score: 77
Acceptable Answer
time: 3263ms
memory: 10056kb

input:

100 222959056 947643239

output:

222959056
358599927
365062242
287299555
872152310
785181552
689517811
751458049
373969559
887125628
238000283
265869067
862846962
717459206
118380127
903859172
38731072
220551290
311944377
678478487
757437607
696077670
937732236
530238679
704937150
7448691
641846446
371506084
393996598
847615147
228...

result:

points 0.770 You got 77 pts!

Test #3:

score: 77
Acceptable Answer
time: 3255ms
memory: 8236kb

input:

100 135352674 235854343

output:

135352674
116843515
129198122
128256418
202034449
101078108
134511179
26177395
38146936
177689345
171471260
220203615
2725266
54489245
202150371
51581049
9159057
174134120
214954721
6858381
164936156
136507834
11983036
56210425
230637079
37588391
129846550
182944624
160550968
143284554
172157415
229...

result:

points 0.770 You got 77 pts!

Test #4:

score: 77
Acceptable Answer
time: 3269ms
memory: 10060kb

input:

100 538608644 566215339

output:

538608644
365236991
134179965
39370099
416828003
17910602
226317362
529379896
407121368
81806097
249408176
336758120
296361261
35236747
429449088
328368699
409154256
418665686
24463075
203118458
352974481
3351773
506522141
61405204
248921056
351694297
485859431
419342548
150905111
157365902
53232656...

result:

points 0.770 You got 77 pts!

Test #5:

score: 77
Acceptable Answer
time: 3259ms
memory: 8184kb

input:

100 56831820 281897771

output:

56831820
213573518
5338712
114481529
104176011
222091299
258318286
168492731
248042852
279768543
163273831
250332871
125456436
55441194
94771937
85241933
265069860
227132810
189427807
26222782
184487649
201740742
267160664
98981147
101908728
84191074
210184730
48919201
18122051
176229976
226118070
1...

result:

points 0.770 You got 77 pts!