QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #497823 | #8728. Tablica | arbuzick# | 59 | 80ms | 36312kb | C++20 | 2.2kb | 2024-07-29 18:46:17 | 2024-07-29 18:46:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int maxn = 205;
int dp[maxn][maxn][maxn];
void solve() {
int n, m;
cin >> n >> m;
dp[0][m][0] = 1;
for (int i = 0; i < n; ++i) {
for (int cnt0 = 0; cnt0 <= m; ++cnt0) {
for (int cnt1 = 0; cnt1 + cnt0 <= m; ++cnt1) {
if (cnt0 > 0) {
dp[i + 1][cnt0 - 1][cnt1 + 1] += dp[i][cnt0][cnt1] * 1LL * cnt0 % mod;
if (dp[i + 1][cnt0 - 1][cnt1 + 1] >= mod) {
dp[i + 1][cnt0 - 1][cnt1 + 1] -= mod;
}
}
if (cnt1 > 0) {
dp[i + 1][cnt0][cnt1 - 1] += dp[i][cnt0][cnt1] * 1LL * cnt1 % mod;
if (dp[i + 1][cnt0][cnt1 - 1] >= mod) {
dp[i + 1][cnt0][cnt1 - 1] -= mod;
}
}
if (cnt0 > 1) {
dp[i + 1][cnt0 - 2][cnt1 + 2] += dp[i][cnt0][cnt1] * 1LL * (cnt0 * 1LL * (cnt0 - 1) / 2 % mod) % mod;
if (dp[i + 1][cnt0 - 2][cnt1 + 2] >= mod) {
dp[i + 1][cnt0 - 2][cnt1 + 2] -= mod;
}
}
if (cnt0 > 0 && cnt1 > 0) {
dp[i + 1][cnt0 - 1][cnt1] += dp[i][cnt0][cnt1] * 1LL * (cnt0 * 1LL * cnt1 % mod) % mod;
if (dp[i + 1][cnt0 - 1][cnt1] >= mod) {
dp[i + 1][cnt0 - 1][cnt1] -= mod;
}
}
if (cnt1 > 1) {
dp[i + 1][cnt0][cnt1 - 2] += dp[i][cnt0][cnt1] * 1LL * (cnt1 * 1LL * (cnt1 - 1) / 2 % mod) % mod;
if (dp[i + 1][cnt0][cnt1 - 2] >= mod) {
dp[i + 1][cnt0][cnt1 - 2] -= mod;
}
}
}
}
}
int ans = 0;
for (int cnt1 = 0; cnt1 <= m; ++cnt1) {
ans += dp[n][0][cnt1];
if (ans >= mod) {
ans -= mod;
}
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3724kb
input:
5 6
output:
456750
result:
ok 1 number(s): "456750"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3624kb
input:
6 6
output:
5464710
result:
ok 1 number(s): "5464710"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3660kb
input:
3 5
output:
270
result:
ok 1 number(s): "270"
Test #4:
score: 10
Accepted
time: 0ms
memory: 3580kb
input:
3 6
output:
90
result:
ok 1 number(s): "90"
Test #5:
score: 10
Accepted
time: 0ms
memory: 3592kb
input:
4 6
output:
14580
result:
ok 1 number(s): "14580"
Test #6:
score: 10
Accepted
time: 0ms
memory: 3584kb
input:
3 4
output:
270
result:
ok 1 number(s): "270"
Subtask #2:
score: 18
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 18
Accepted
time: 3ms
memory: 5752kb
input:
50 49
output:
750700714
result:
ok 1 number(s): "750700714"
Test #8:
score: 18
Accepted
time: 3ms
memory: 5808kb
input:
50 50
output:
630532893
result:
ok 1 number(s): "630532893"
Test #9:
score: 18
Accepted
time: 1ms
memory: 4872kb
input:
41 34
output:
800856205
result:
ok 1 number(s): "800856205"
Test #10:
score: 18
Accepted
time: 2ms
memory: 5112kb
input:
39 41
output:
541550932
result:
ok 1 number(s): "541550932"
Test #11:
score: 18
Accepted
time: 2ms
memory: 5232kb
input:
38 46
output:
651393374
result:
ok 1 number(s): "651393374"
Test #12:
score: 18
Accepted
time: 0ms
memory: 4980kb
input:
37 39
output:
746919932
result:
ok 1 number(s): "746919932"
Test #13:
score: 18
Accepted
time: 0ms
memory: 4860kb
input:
30 50
output:
214086425
result:
ok 1 number(s): "214086425"
Test #14:
score: 18
Accepted
time: 2ms
memory: 5448kb
input:
50 41
output:
193351204
result:
ok 1 number(s): "193351204"
Test #15:
score: 18
Accepted
time: 1ms
memory: 4852kb
input:
44 32
output:
63855946
result:
ok 1 number(s): "63855946"
Test #16:
score: 18
Accepted
time: 2ms
memory: 5284kb
input:
45 42
output:
266239299
result:
ok 1 number(s): "266239299"
Subtask #3:
score: 31
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #17:
score: 31
Accepted
time: 72ms
memory: 36216kb
input:
199 200
output:
841552647
result:
ok 1 number(s): "841552647"
Test #18:
score: 31
Accepted
time: 80ms
memory: 36312kb
input:
200 200
output:
157842226
result:
ok 1 number(s): "157842226"
Test #19:
score: 31
Accepted
time: 39ms
memory: 28988kb
input:
156 199
output:
216453917
result:
ok 1 number(s): "216453917"
Test #20:
score: 31
Accepted
time: 60ms
memory: 29780kb
input:
161 199
output:
539960909
result:
ok 1 number(s): "539960909"
Test #21:
score: 31
Accepted
time: 48ms
memory: 29168kb
input:
194 160
output:
764024671
result:
ok 1 number(s): "764024671"
Test #22:
score: 31
Accepted
time: 51ms
memory: 33028kb
input:
184 195
output:
117763744
result:
ok 1 number(s): "117763744"
Test #23:
score: 31
Accepted
time: 52ms
memory: 25208kb
input:
152 174
output:
350941677
result:
ok 1 number(s): "350941677"
Test #24:
score: 31
Accepted
time: 62ms
memory: 33276kb
input:
195 186
output:
130526660
result:
ok 1 number(s): "130526660"
Test #25:
score: 31
Accepted
time: 27ms
memory: 26220kb
input:
173 159
output:
754934766
result:
ok 1 number(s): "754934766"
Test #26:
score: 31
Accepted
time: 59ms
memory: 30652kb
input:
194 170
output:
956364877
result:
ok 1 number(s): "956364877"
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 0
Time Limit Exceeded
input:
3000 2999