QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#930482#8728. TablicaCyanmond59 68ms3968kbC++232.5kb2025-03-09 21:56:272025-03-09 21:56:28

Judging History

This is the latest submission verdict.

  • [2025-03-09 21:56:28]
  • Judged
  • Verdict: 59
  • Time: 68ms
  • Memory: 3968kb
  • [2025-03-09 21:56:27]
  • Submitted

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

output:


result: