QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#890251#1084. Beautiful Sequence Unravelingxwh_MarvelousAC ✓1008ms5376kbC++141.3kb2025-02-08 21:04:302025-02-08 21:04:31

Judging History

This is the latest submission verdict.

  • [2025-02-08 21:04:31]
  • Judged
  • Verdict: AC
  • Time: 1008ms
  • Memory: 5376kb
  • [2025-02-08 21:04:30]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 505
//#define pii pair<int,int>
//#define fi first
//#define se second
//#define rep(i,j,k) for(int i=j;i<=k;i++)
int f[N][N],a[N],b[N],c[N];
int n,m,mod;
int fpow(int x,int y){
	int ret=1,op=x;
	op%=mod;
	while(y){
		if(y&1)ret=ret*op%mod;
		op=op*op%mod;
		y>>=1;
	}
	return ret;
}
int g[N];
int C(int n,int m){
	if(m>n)return 0;
	if(n-m<m)m=n-m;
	int a=1,b=1;
	for(int i=1;i<=m;i++)a=a*(n-i+1)%mod,b=b*i%mod;
	return a*fpow(b,mod-2)%mod;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>mod;
	for(int i=1;i<=n;i++)f[1][i]=i;
	for(int y=1;y<=n;y++){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		for(int x=2;x<=n;x++){
			for(int j=1;j<=y;j++)a[j]=(a[j]+f[x-1][y-(j-1)])%mod*j%mod;
			for(int j=1;j<=y;j++)b[j]=(b[j]+f[x-1][y-j])%mod*j%mod;
			for(int j=1;j<y;j++)c[j]=(c[j]+f[x-1][y-(j+1)])%mod*j%mod;
			f[x][y]=fpow(y,x);
			for(int j=1;j<=y;j++){
				f[x][y]=((f[x][y]-a[j]+b[j-1]+b[j]-c[j-1])%mod+mod)%mod;
			}
			// cout<<f[x][y]<<' ';
		}//cout<<endl;
	}
	for(int i=1;i<=n;i++){
		g[i]=f[n][i];
		for(int j=1;j<i;j++){
			g[i]=(g[i]-C(i,j)*g[j]%mod+mod)%mod;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=(ans+C(m,i)*g[i])%mod;
	cout<<ans;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 190ms
memory: 4480kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 1008ms
memory: 5248kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 1003ms
memory: 5376kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

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

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

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

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 1003ms
memory: 5248kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 1004ms
memory: 5248kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 1004ms
memory: 5248kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 1007ms
memory: 5248kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 1000ms
memory: 5248kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 990ms
memory: 5248kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 983ms
memory: 5248kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"