QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#863810 | #8116. Kocke | Unforgettablepl | 80 | 762ms | 493368kb | C++20 | 1.2kb | 2025-01-19 22:50:41 | 2025-01-19 22:50:44 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int modulo = 1e9+7;
int DP[501][125250][2];
int lookup[501][501];
int32_t main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n,K;
cin >> n >> K;
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';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 6708kb
input:
2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 20
Accepted
time: 1ms
memory: 10224kb
input:
5 18
output:
218
result:
ok single line: '218'
Test #3:
score: 20
Accepted
time: 0ms
memory: 14860kb
input:
9 18
output:
1980
result:
ok single line: '1980'
Test #4:
score: 20
Accepted
time: 0ms
memory: 20628kb
input:
15 9
output:
9564
result:
ok single line: '9564'
Test #5:
score: 20
Accepted
time: 0ms
memory: 20956kb
input:
16 18
output:
66116
result:
ok single line: '66116'
Test #6:
score: 20
Accepted
time: 0ms
memory: 23092kb
input:
18 10
output:
43140
result:
ok single line: '43140'
Test #7:
score: 20
Accepted
time: 0ms
memory: 23092kb
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: 1ms
memory: 7860kb
input:
2 49
output:
96
result:
ok single line: '96'
Test #9:
score: 30
Accepted
time: 0ms
memory: 10804kb
input:
7 38
output:
1598
result:
ok single line: '1598'
Test #10:
score: 30
Accepted
time: 0ms
memory: 25136kb
input:
19 6
output:
5524
result:
ok single line: '5524'
Test #11:
score: 30
Accepted
time: 0ms
memory: 36700kb
input:
31 49
output:
369127208
result:
ok single line: '369127208'
Test #12:
score: 30
Accepted
time: 0ms
memory: 49772kb
input:
44 30
output:
310756420
result:
ok single line: '310756420'
Test #13:
score: 30
Accepted
time: 0ms
memory: 51768kb
input:
49 2
output:
2
result:
ok single line: '2'
Test #14:
score: 30
Accepted
time: 1ms
memory: 55256kb
input:
50 50
output:
375733561
result:
ok single line: '375733561'
Subtask #3:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #15:
score: 30
Accepted
time: 0ms
memory: 8888kb
input:
2 319
output:
636
result:
ok single line: '636'
Test #16:
score: 30
Accepted
time: 0ms
memory: 93932kb
input:
89 44
output:
999831996
result:
ok single line: '999831996'
Test #17:
score: 30
Accepted
time: 113ms
memory: 281076kb
input:
280 279
output:
332244975
result:
ok single line: '332244975'
Test #18:
score: 30
Accepted
time: 312ms
memory: 283140kb
input:
282 500
output:
344135056
result:
ok single line: '344135056'
Test #19:
score: 30
Accepted
time: 136ms
memory: 427232kb
input:
464 211
output:
629248621
result:
ok single line: '629248621'
Test #20:
score: 30
Accepted
time: 762ms
memory: 493368kb
input:
499 500
output:
732883324
result:
ok single line: '732883324'
Test #21:
score: 30
Accepted
time: 0ms
memory: 428696kb
input:
500 2
output:
2
result:
ok single line: '2'
Test #22:
score: 30
Accepted
time: 346ms
memory: 491204kb
input:
500 324
output:
992004807
result:
ok single line: '992004807'
Subtask #4:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #23:
score: 0
Wrong Answer
time: 84ms
memory: 7584kb
input:
2 4999
output:
33808864
result:
wrong answer 1st lines differ - expected: '9996', found: '33808864'