QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397288 | #8116. Kocke | lfxxx# | 80 | 104ms | 22384kb | C++14 | 1.2kb | 2024-04-23 21:28:17 | 2024-07-04 03:37:11 |
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][2];
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][0] = f[2][n - 1][1] = 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][0] = f[i][j][1] = 0;
for (int k = 0; j + 1 + 2 * k <= n; ++k) {
f[i][j][0] = (f[i][j][0] + f[i - 1][j + 1 + 2 * k][0]) % mod;
f[i][j][1] = (f[i][j][1] + f[i - 1][j + 1 + 2 * k][1]) % mod;
}
for (int k = 0; i + j - 1 + 2 * k <= n; ++k) {
f[i][j][0] = (f[i][j][0] + f[i - 1][i + j - 1 + 2 * k][1]) % mod;
f[i][j][1] = (f[i][j][1] + f[i - 1][i + j - 1 + 2 * k][0]) % mod;
}
ans = (ans + (ll) (f[i][j][0] + f[i][j][1]) * (k - i + 1)) % mod;
}
}
cout << ans << endl;
return 0;
}
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 1ms
memory: 3520kb
input:
2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
5 18
output:
218
result:
ok single line: '218'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
9 18
output:
1980
result:
ok single line: '1980'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
15 9
output:
9564
result:
ok single line: '9564'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
16 18
output:
66116
result:
ok single line: '66116'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
18 10
output:
43140
result:
ok single line: '43140'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3708kb
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: 3692kb
input:
2 49
output:
96
result:
ok single line: '96'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
7 38
output:
1598
result:
ok single line: '1598'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
19 6
output:
5524
result:
ok single line: '5524'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
31 49
output:
369127208
result:
ok single line: '369127208'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
44 30
output:
310756420
result:
ok single line: '310756420'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
49 2
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5748kb
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: 3716kb
input:
2 319
output:
636
result:
ok single line: '636'
Test #16:
score: 0
Accepted
time: 2ms
memory: 5836kb
input:
89 44
output:
999831996
result:
ok single line: '999831996'
Test #17:
score: 0
Accepted
time: 17ms
memory: 13920kb
input:
280 279
output:
332244975
result:
ok single line: '332244975'
Test #18:
score: 0
Accepted
time: 18ms
memory: 14032kb
input:
282 500
output:
344135056
result:
ok single line: '344135056'
Test #19:
score: 0
Accepted
time: 63ms
memory: 11908kb
input:
464 211
output:
629248621
result:
ok single line: '629248621'
Test #20:
score: 0
Accepted
time: 104ms
memory: 22384kb
input:
499 500
output:
732883324
result:
ok single line: '732883324'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
500 2
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 90ms
memory: 16108kb
input:
500 324
output:
992004807
result:
ok single line: '992004807'
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #23:
score: 30
Accepted
time: 0ms
memory: 3648kb
input:
2 4999
output:
9996
result:
ok single line: '9996'
Test #24:
score: -30
Time Limit Exceeded
input:
1988 4702