QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#863777	#8116. Kocke	Unforgettablepl	50	12ms	26240kb	C++20	904b	2025-01-19 22:11:15	2025-01-19 22:11:21

Judging History

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

[2025-01-19 22:11:21]
评测

测评结果：50
用时：12ms
内存：26240kb

查看

[2025-01-19 22:11:15]
提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long


const int modulo = 1e9+7;

int32_t main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n,K;
	cin >> n >> K;
	vector DP(n+1,vector(K+1,vector(K+1,vector(2,0ll))));
	for(int i=1;i<=K;i++)DP[1][i][i][0]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=K;j++){
			for(int k=j+1;k<=K;k++){
				DP[i][j][k][0]=DP[i-2][j][k][0]+DP[i-1][j+1][k][0];
				if(i-(k-j)>=1)DP[i][j][k][0]+=DP[i-(k-j)][j+1][k][1];
				DP[i][j][k][0]%=modulo;

				DP[i][j][k][1]=DP[i-2][j][k][1]+DP[i-1][j][k-1][1];
				if(i-(k-j)>=1)DP[i][j][k][1]+=DP[i-(k-j)][j][k-1][0];
				DP[i][j][k][1]%=modulo;
			}
		}
	}
	int ans = 0;
	for(int l=1;l<=K;l++){
		for(int r=l+1;r<=K;r++){
			ans = (ans+DP[n][l][r][0]+DP[n][l][r][1])%modulo;
			ans = (ans+DP[n-1][l][r][0]+DP[n-1][l][r][1])%modulo;
		}
	}
	cout << ans << '\n';
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 20

Accepted

Test #1:

score: 20

Accepted

time: 0ms

memory: 3712kb

input:

2 3

output:

result:

ok single line: '4'

Test #2:

score: 20

Accepted

time: 1ms

memory: 3712kb

input:

5 18

output:

result:

ok single line: '218'

Test #3:

score: 20

Accepted

time: 1ms

memory: 3840kb

input:

9 18

output:

result:

ok single line: '1980'

Test #4:

score: 20

Accepted

time: 1ms

memory: 3712kb

input:

15 9

output:

result:

ok single line: '9564'

Test #5:

score: 20

Accepted

time: 1ms

memory: 4096kb

input:

16 18

output:

result:

ok single line: '66116'

Test #6:

score: 20

Accepted

time: 1ms

memory: 3840kb

input:

18 10

output:

result:

ok single line: '43140'

Test #7:

score: 20

Accepted

time: 0ms

memory: 4096kb

input:

18 18

output:

result:

ok single line: '170888'

Subtask #2:

score: 30

Accepted

Dependency #1:

100%

Accepted

Test #8:

score: 30

Accepted

time: 1ms

memory: 4352kb

input:

2 49

output:

result:

ok single line: '96'

Test #9:

score: 30

Accepted

time: 0ms

memory: 4480kb

input:

7 38

output:

result:

ok single line: '1598'

Test #10:

score: 30

Accepted

time: 0ms

memory: 3840kb

input:

19 6

output:

result:

ok single line: '5524'

Test #11:

score: 30

Accepted

time: 2ms

memory: 8320kb

input:

31 49

output:

369127208

result:

ok single line: '369127208'

Test #12:

score: 30

Accepted

time: 1ms

memory: 6144kb

input:

44 30

output:

310756420

result:

ok single line: '310756420'

Test #13:

score: 30

Accepted

time: 1ms

memory: 3840kb

input:

49 2

output:

result:

ok single line: '2'

Test #14:

score: 30

Accepted

time: 4ms

memory: 11136kb

input:

50 50

output:

375733561

result:

ok single line: '375733561'

Subtask #3:

score: 0

Memory Limit Exceeded

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #15:

score: 30

Accepted

time: 12ms

memory: 26240kb

input:

2 319

output:

result:

ok single line: '636'

Test #16:

score: 30

Accepted

time: 6ms

memory: 13696kb

input:

89 44

output:

999831996

result:

ok single line: '999831996'

Test #17:

score: 0

Memory Limit Exceeded

input:

280 279

output:

332244975

result:

Subtask #4:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted