QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32650#1084. Beautiful Sequence UnravelingWu_RenAC ✓1214ms7064kbC++171.2kb2022-05-22 20:24:322022-05-22 20:24:33

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-22 20:24:33]
  • Judged
  • Verdict: AC
  • Time: 1214ms
  • Memory: 7064kb
  • [2022-05-22 20:24:32]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
int mod;
int n,K,inv[410][410],_k[410][410],g[410][410],f[410][410],h[410],C[410][410];
void qmo(int &x){
	x+=(x>>31)&mod;
}
void init(int N){
	inv[1][1]=1;
	for(int i=2;i<=N;i++) inv[i][1]=mod-1ll*(mod/i)*inv[mod%i][1]%mod;
	for(int i=1;i<=N;i++){
		inv[i][0]=_k[i][0]=1,_k[i][1]=i;
		for(int j=2;j<=N;j++){
			inv[i][j]=1ll*inv[i][j-1]*inv[i][1]%mod;//i^{-j}
			_k[i][j]=1ll*_k[i][j-1]*i%mod;//i^j
		}
	}
	for(int i=0;i<=N;i++) for(int j=C[i][0]=1;j<=i;j++) qmo(C[i][j]=C[i-1][j-1]+C[i-1][j]-mod);
}
int main(){
	scanf("%d%d%d",&n,&K,&mod),init(n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=_k[j][i];
			for(int y=1;y<=j;y++){
				f[i][j]=(f[i][j]-1ll*_k[y][i]*(g[j-y+1][y]-g[j-y][y]+mod)%mod+mod+1ll*_k[y-1][i]*(g[j-y+1][y-1]-g[j-y][y-1]+mod))%mod;
			}
//			printf("f[%d][%d]=%d\n",i,j,f[i][j]);
		}
		for(int j=1;j<=n;j++) for(int y=1;y<=n;y++) g[j][y]=(g[j][y]+1ll*f[i][j]*inv[y][i])%mod;
	}
	int CK=1,ans=0;
	for(int i=1;i<=n;i++){
		CK=1ll*CK*(K-i+1)%mod*inv[i][1]%mod;
		h[i]=f[n][i];
		for(int j=1;j<i;j++) qmo(h[i]-=1ll*h[j]*C[i][j]%mod);
		ans=(ans+1ll*h[i]*CK)%mod;
	}
	printf("%d\n",ans);
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3812kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 3ms
memory: 5832kb

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 220ms
memory: 5628kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

score: 0
Accepted
time: 0ms
memory: 5844kb

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 3ms
memory: 3772kb

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 1168ms
memory: 6996kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 1173ms
memory: 6952kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 3ms
memory: 5852kb

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

score: 0
Accepted
time: 3ms
memory: 5820kb

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 1214ms
memory: 6876kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 1171ms
memory: 6988kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 1174ms
memory: 6996kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 1178ms
memory: 7064kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 1168ms
memory: 6960kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 1156ms
memory: 6972kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 1154ms
memory: 6864kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"