QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#930482 | #8728. Tablica | Cyanmond | 59 | 68ms | 3968kb | C++23 | 2.5kb | 2025-03-09 21:56:27 | 2025-03-09 21:56:28 |
Judging History
answer
#include <bits/stdc++.h>
#define AOTSUKI
using namespace std;
constexpr bool isMultiCase = 0;
// #include "angel/math/modint.hpp"
using ll = long long;
template <class T> constexpr int len(const T &c) {
return int(std::ssize(c));
}
template <class T> using V = vector<T>;
template <class T> using RevPq = priority_queue<T, vector<T>, greater<T>>;
constexpr char eoln = '\n';
#define L(i, l, r) for (int i = (l); i < (r); ++i)
#define R(i, l, r) for (int i = (r) - 1; i >= (l); --i)
#define ALL(x) (x).begin(), (x).end()
#define fi first
#define se second
constexpr ll mod = 1000000007;
void solve() {
int n, m; cin >> n >> m;
vector dp(m + 1, vector(m + 1, 0ll));
dp[m][0] = 1;
L(t, 0, n) {
vector ndp(m + 1, vector(m + 1, 0ll));
L(i, 0, m + 1) {
L(j, 0, m + 1) {
// case 1 : choose 1
// case 1-1 : choose (1, 0)
if (i != 0 and j != m) {
ndp[i - 1][j + 1] += dp[i][j] * i;
ndp[i - 1][j + 1] %= mod;
}
// case 1-2 : choose (0, 1)
if (j != 0) {
ndp[i][j - 1] += dp[i][j] * j;
ndp[i][j - 1] %= mod;
}
// case 2 : choose 2
// case 2-1 : choose (2, 0)
if (i >= 2 and j <= m - 2) {
ndp[i - 2][j + 2] += dp[i][j] * i * (i - 1) / 2;
ndp[i - 2][j + 2] %= mod;
}
// case 2-2 : choose (1, 1)
if (i != 0) {
ndp[i - 1][j] += dp[i][j] * i * j;
ndp[i - 1][j] %= mod;
}
// case 2-3 : choose (2, 0)
if (j >= 2) {
ndp[i][j - 2] += dp[i][j] * j * (j - 1) / 2;
ndp[i][j - 2] %= mod;
}
}
}
/*
L(i, 0, m + 1) {
L(j, 0, m + 1) {
cerr << ndp[i][j] << ' ';
}
cerr << endl;
}
cerr << endl;
*/
dp = move(ndp);
}
ll ans = 0;
L(i, 0, m + 1) ans += dp[0][i];
ans %= mod;
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (not isMultiCase) {
solve();
} else {
int t;
cin >> t;
while (t--) solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3584kb
input:
5 6
output:
456750
result:
ok 1 number(s): "456750"
Test #2:
score: 10
Accepted
time: 0ms
memory: 3584kb
input:
6 6
output:
5464710
result:
ok 1 number(s): "5464710"
Test #3:
score: 10
Accepted
time: 0ms
memory: 3584kb
input:
3 5
output:
270
result:
ok 1 number(s): "270"
Test #4:
score: 10
Accepted
time: 1ms
memory: 3584kb
input:
3 6
output:
90
result:
ok 1 number(s): "90"
Test #5:
score: 10
Accepted
time: 1ms
memory: 3584kb
input:
4 6
output:
14580
result:
ok 1 number(s): "14580"
Test #6:
score: 10
Accepted
time: 1ms
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: 2ms
memory: 3712kb
input:
50 49
output:
750700714
result:
ok 1 number(s): "750700714"
Test #8:
score: 18
Accepted
time: 1ms
memory: 3712kb
input:
50 50
output:
630532893
result:
ok 1 number(s): "630532893"
Test #9:
score: 18
Accepted
time: 1ms
memory: 3584kb
input:
41 34
output:
800856205
result:
ok 1 number(s): "800856205"
Test #10:
score: 18
Accepted
time: 1ms
memory: 3712kb
input:
39 41
output:
541550932
result:
ok 1 number(s): "541550932"
Test #11:
score: 18
Accepted
time: 1ms
memory: 3712kb
input:
38 46
output:
651393374
result:
ok 1 number(s): "651393374"
Test #12:
score: 18
Accepted
time: 1ms
memory: 3584kb
input:
37 39
output:
746919932
result:
ok 1 number(s): "746919932"
Test #13:
score: 18
Accepted
time: 1ms
memory: 3712kb
input:
30 50
output:
214086425
result:
ok 1 number(s): "214086425"
Test #14:
score: 18
Accepted
time: 1ms
memory: 3712kb
input:
50 41
output:
193351204
result:
ok 1 number(s): "193351204"
Test #15:
score: 18
Accepted
time: 0ms
memory: 3584kb
input:
44 32
output:
63855946
result:
ok 1 number(s): "63855946"
Test #16:
score: 18
Accepted
time: 0ms
memory: 3712kb
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: 68ms
memory: 3968kb
input:
199 200
output:
841552647
result:
ok 1 number(s): "841552647"
Test #18:
score: 31
Accepted
time: 66ms
memory: 3968kb
input:
200 200
output:
157842226
result:
ok 1 number(s): "157842226"
Test #19:
score: 31
Accepted
time: 50ms
memory: 3840kb
input:
156 199
output:
216453917
result:
ok 1 number(s): "216453917"
Test #20:
score: 31
Accepted
time: 56ms
memory: 3968kb
input:
161 199
output:
539960909
result:
ok 1 number(s): "539960909"
Test #21:
score: 31
Accepted
time: 45ms
memory: 3812kb
input:
194 160
output:
764024671
result:
ok 1 number(s): "764024671"
Test #22:
score: 31
Accepted
time: 59ms
memory: 3968kb
input:
184 195
output:
117763744
result:
ok 1 number(s): "117763744"
Test #23:
score: 31
Accepted
time: 37ms
memory: 3740kb
input:
152 174
output:
350941677
result:
ok 1 number(s): "350941677"
Test #24:
score: 31
Accepted
time: 58ms
memory: 3712kb
input:
195 186
output:
130526660
result:
ok 1 number(s): "130526660"
Test #25:
score: 31
Accepted
time: 36ms
memory: 3724kb
input:
173 159
output:
754934766
result:
ok 1 number(s): "754934766"
Test #26:
score: 31
Accepted
time: 47ms
memory: 3796kb
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