QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#888078#1084. Beautiful Sequence UnravelingqwqUwU_AC ✓262ms4864kbC++141.0kb2025-02-07 21:55:582025-02-07 21:55:58

Judging History

This is the latest submission verdict.

  • [2025-02-07 21:55:58]
  • Judged
  • Verdict: AC
  • Time: 262ms
  • Memory: 4864kb
  • [2025-02-07 21:55:58]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int mod;
inline int fp(int x,int p=mod-2,int res=1){
	for(;p;p>>=1){if(p&1)res=1ll*res*x%mod;x=1ll*x*x%mod;}
	return res;
}
inline void Ad(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void Mi(int &x,int y){x=x-y<0?x-y+mod:x-y;}
const int N=402;
int n,K,f[N][N],C[N][N],g[N],c[N];
int main() {
	cin>>n>>K>>mod;
	rep(i,0,n){
		C[i][0]=1;
		rep(j,1,i)Ad(C[i][j]=C[i-1][j],C[i-1][j-1]);
	}
	rep(j,1,n){
		f[j][1]=j;
		rep(i,2,n)f[j][i]=1ll*f[j][i-1]*j%mod;
		per(k,j,1){
			int a[2];
			rep(d,0,1)a[d]=0;
			rep(i,1,n){
				Ad(f[j][i],a[1]),Mi(f[j][i],a[0]);
				rep(d,0,1)a[d]=1ll*(k-d)*(1ll*a[d]+f[j-k+1][i]-f[j-k][i]+mod)%mod;
			}
		}
	}
	rep(j,1,n){
		g[j]=f[j][n];
		rep(i,1,j-1)Mi(g[j],1ll*C[j][i]*g[i]%mod);
	}
	c[0]=1;
	rep(i,1,n)c[i]=1ll*c[i-1]*fp(i)%mod*(K-i+1)%mod;
	int ans=0;
	rep(i,1,n)Ad(ans,1ll*c[i]*g[i]%mod);
	cout<<ans;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3456kb

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: 49ms
memory: 4096kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

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: 1ms
memory: 3584kb

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 262ms
memory: 4608kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 262ms
memory: 4608kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

score: 0
Accepted
time: 0ms
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: 1ms
memory: 3328kb

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 261ms
memory: 4736kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 261ms
memory: 4736kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 261ms
memory: 4608kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 259ms
memory: 4608kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 260ms
memory: 4864kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 257ms
memory: 4864kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 255ms
memory: 4736kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"