QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397299 | #8116. Kocke | lfxxx# | 110 ✓ | 68ms | 168568kb | C++14 | 904b | 2024-04-23 21:43:03 | 2024-07-04 03:37:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 5005, mod = 1e9 + 7;
int n, k, f[N][N], sum[N][N];
bool en;
int main()
{
#ifdef IAKIOI
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n-------------------\n";
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
f[2][n - 1] = 1;
for (int i = n - 1; i >= 1; i -= 2) sum[2][i] = 1;
int ans = 2 * (k - 1);
for (int i = 3; i <= min(n, k); ++i) {
for (int j = n - i + 1; j >= 1; --j) {
f[i][j] = (sum[i - 1][j + 1] + sum[i - 1][i + j - 1]) % mod;
ans = (ans + (ll) (f[i][j] * 2) * (k - i + 1)) % mod;
sum[i][j] = (sum[i][j + 2] + f[i][j]) % mod;
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 1ms
memory: 5568kb
input:
2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
5 18
output:
218
result:
ok single line: '218'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
9 18
output:
1980
result:
ok single line: '1980'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
15 9
output:
9564
result:
ok single line: '9564'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5688kb
input:
16 18
output:
66116
result:
ok single line: '66116'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5644kb
input:
18 10
output:
43140
result:
ok single line: '43140'
Test #7:
score: 0
Accepted
time: 0ms
memory: 7728kb
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: 5616kb
input:
2 49
output:
96
result:
ok single line: '96'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5716kb
input:
7 38
output:
1598
result:
ok single line: '1598'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
19 6
output:
5524
result:
ok single line: '5524'
Test #11:
score: 0
Accepted
time: 0ms
memory: 5732kb
input:
31 49
output:
369127208
result:
ok single line: '369127208'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5716kb
input:
44 30
output:
310756420
result:
ok single line: '310756420'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
49 2
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5956kb
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: 1ms
memory: 7744kb
input:
2 319
output:
636
result:
ok single line: '636'
Test #16:
score: 0
Accepted
time: 1ms
memory: 7836kb
input:
89 44
output:
999831996
result:
ok single line: '999831996'
Test #17:
score: 0
Accepted
time: 2ms
memory: 11124kb
input:
280 279
output:
332244975
result:
ok single line: '332244975'
Test #18:
score: 0
Accepted
time: 0ms
memory: 14620kb
input:
282 500
output:
344135056
result:
ok single line: '344135056'
Test #19:
score: 0
Accepted
time: 0ms
memory: 10864kb
input:
464 211
output:
629248621
result:
ok single line: '629248621'
Test #20:
score: 0
Accepted
time: 0ms
memory: 18392kb
input:
499 500
output:
732883324
result:
ok single line: '732883324'
Test #21:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
500 2
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 0ms
memory: 13620kb
input:
500 324
output:
992004807
result:
ok single line: '992004807'
Subtask #4:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #23:
score: 30
Accepted
time: 0ms
memory: 5684kb
input:
2 4999
output:
9996
result:
ok single line: '9996'
Test #24:
score: 0
Accepted
time: 11ms
memory: 60248kb
input:
1988 4702
output:
182266147
result:
ok single line: '182266147'
Test #25:
score: 0
Accepted
time: 21ms
memory: 74964kb
input:
2500 5000
output:
765321947
result:
ok single line: '765321947'
Test #26:
score: 0
Accepted
time: 38ms
memory: 146524kb
input:
4388 4717
output:
253964546
result:
ok single line: '253964546'
Test #27:
score: 0
Accepted
time: 44ms
memory: 155032kb
input:
4611 4812
output:
467863120
result:
ok single line: '467863120'
Test #28:
score: 0
Accepted
time: 1ms
memory: 5712kb
input:
4825 2
output:
2
result:
ok single line: '2'
Test #29:
score: 0
Accepted
time: 1ms
memory: 5644kb
input:
5000 3
output:
10000
result:
ok single line: '10000'
Test #30:
score: 0
Accepted
time: 68ms
memory: 168568kb
input:
5000 5000
output:
325667260
result:
ok single line: '325667260'
Extra Test:
score: 0
Extra Test Passed