QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #863795 | #8116. Kocke | Unforgettablepl | 50 | 228ms | 359260kb | C++20 | 1.2kb | 2025-01-19 22:34:38 | 2025-01-19 22:34:39 |
Judging History
answer
#pragma GCC optimize("Os")
#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(125250,vector<int>(2,0)));
vector lookup(501,vector(501,0));
int cnt = 0;
for(int i=1;i<=500;i++){
for(int j=i;j<=500;j++){
lookup[i][j]=cnt++;
}
}
for(int i=1;i<=K;i++)DP[1][lookup[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][lookup[j][k]][0]=(DP[i-2][lookup[j][k]][0]+DP[i-1][lookup[j+1][k]][0])%modulo;
if(i-(k-j)>=1)DP[i][lookup[j][k]][0]=(DP[i][lookup[j][k]][0]+DP[i-(k-j)][lookup[j+1][k]][1])%modulo;
DP[i][lookup[j][k]][1]=(DP[i-2][lookup[j][k]][1]+DP[i-1][lookup[j][k-1]][1])%modulo;
if(i-(k-j)>=1)DP[i][lookup[j][k]][1]=(DP[i][lookup[j][k]][1]+DP[i-(k-j)][lookup[j][k-1]][0])%modulo;
}
}
}
long long ans = 0;
for(int l=1;l<=K;l++){
for(int r=l+1;r<=K;r++){
ans += (DP[n][lookup[l][r]][0]+DP[n][lookup[l][r]][1])%modulo;
ans += (DP[n-1][lookup[l][r]][0]+DP[n-1][lookup[l][r]][1])%modulo;
ans%=modulo;
}
}
cout << ans << '\n';
}
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 15ms
memory: 30580kb
input:
2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 20
Accepted
time: 27ms
memory: 51120kb
input:
5 18
output:
218
result:
ok single line: '218'
Test #3:
score: 20
Accepted
time: 34ms
memory: 78360kb
input:
9 18
output:
1980
result:
ok single line: '1980'
Test #4:
score: 20
Accepted
time: 66ms
memory: 119596kb
input:
15 9
output:
9564
result:
ok single line: '9564'
Test #5:
score: 20
Accepted
time: 61ms
memory: 126468kb
input:
16 18
output:
66116
result:
ok single line: '66116'
Test #6:
score: 20
Accepted
time: 69ms
memory: 140228kb
input:
18 10
output:
43140
result:
ok single line: '43140'
Test #7:
score: 20
Accepted
time: 69ms
memory: 140120kb
input:
18 18
output:
170888
result:
ok single line: '170888'
Subtask #2:
score: 30
Accepted
Dependency #1:
100%
Accepted
Test #8:
score: 30
Accepted
time: 12ms
memory: 30628kb
input:
2 49
output:
96
result:
ok single line: '96'
Test #9:
score: 30
Accepted
time: 26ms
memory: 64880kb
input:
7 38
output:
1598
result:
ok single line: '1598'
Test #10:
score: 30
Accepted
time: 72ms
memory: 147080kb
input:
19 6
output:
5524
result:
ok single line: '5524'
Test #11:
score: 30
Accepted
time: 117ms
memory: 229160kb
input:
31 49
output:
369127208
result:
ok single line: '369127208'
Test #12:
score: 30
Accepted
time: 185ms
memory: 318244kb
input:
44 30
output:
310756420
result:
ok single line: '310756420'
Test #13:
score: 30
Accepted
time: 202ms
memory: 352544kb
input:
49 2
output:
2
result:
ok single line: '2'
Test #14:
score: 30
Accepted
time: 228ms
memory: 359260kb
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: 14ms
memory: 30632kb
input:
2 319
output:
636
result:
ok single line: '636'
Test #16:
score: 0
Memory Limit Exceeded
input:
89 44
output:
999831996
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%