QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#930586#8728. TablicaCyanmond59 62ms199304kbC++232.1kb2025-03-10 00:42:162025-03-10 00:42:24

Judging History

This is the latest submission verdict.

  • [2025-03-10 00:42:24]
  • Judged
  • Verdict: 59
  • Time: 62ms
  • Memory: 199304kb
  • [2025-03-10 00:42:16]
  • 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;

constexpr int MaxN = 5000;
ll comb[MaxN + 1][MaxN + 1];
ll fact[MaxN + 1];
ll pw2[MaxN + 1], ipw2[MaxN + 1];
constexpr ll i2 = 500000004;

void init() {
    L(i, 0, MaxN + 1) L(j, 0, MaxN + 1) comb[i][j] = 0;
    comb[0][0] = 1;
    L(i, 1, MaxN + 1) {
        comb[i][0] = 1;
        L(j, 1, i + 1) {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
            comb[i][j] %= mod;
        }
    }
    fact[0] = pw2[0] = ipw2[0] = 1;
    L(i, 1, MaxN + 1) {
        fact[i] = fact[i - 1] * i % mod;
        pw2[i] = pw2[i - 1] * 2 % mod;
        ipw2[i] = ipw2[i - 1] * i2 % mod;
    }
}

void solve() {
    int n, m; cin >> n >> m;
    ll ans = 0;

    L(a, 0, n + 1) {
        // a : degree 2
        int b = n + a - m;
        if (b < 0 or b > m) continue;

        ll sc = 0;
        L(p, 0, min(a, b) + 1) {
            ll sign = p & 1 ? mod - 1 : 1;
            ll val = comb[a][p] * comb[b][p] % mod * fact[p] % mod * pw2[p] % mod;
            val *= fact[n + a - 2 * p]; val %= mod;
            sc += sign * val; sc %= mod;
        }
        sc *= comb[n][a] % mod * comb[m][b] % mod * ipw2[a + b] % mod; sc %= mod;
        ans += sc;
    }
    ans %= mod;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    init();
    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: 26ms
memory: 199064kb

input:

5 6

output:

456750

result:

ok 1 number(s): "456750"

Test #2:

score: 10
Accepted
time: 28ms
memory: 199140kb

input:

6 6

output:

5464710

result:

ok 1 number(s): "5464710"

Test #3:

score: 10
Accepted
time: 23ms
memory: 199104kb

input:

3 5

output:

270

result:

ok 1 number(s): "270"

Test #4:

score: 10
Accepted
time: 22ms
memory: 199216kb

input:

3 6

output:

90

result:

ok 1 number(s): "90"

Test #5:

score: 10
Accepted
time: 21ms
memory: 199096kb

input:

4 6

output:

14580

result:

ok 1 number(s): "14580"

Test #6:

score: 10
Accepted
time: 22ms
memory: 199164kb

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: 21ms
memory: 199304kb

input:

50 49

output:

750700714

result:

ok 1 number(s): "750700714"

Test #8:

score: 18
Accepted
time: 25ms
memory: 199244kb

input:

50 50

output:

630532893

result:

ok 1 number(s): "630532893"

Test #9:

score: 18
Accepted
time: 25ms
memory: 199140kb

input:

41 34

output:

800856205

result:

ok 1 number(s): "800856205"

Test #10:

score: 18
Accepted
time: 20ms
memory: 199236kb

input:

39 41

output:

541550932

result:

ok 1 number(s): "541550932"

Test #11:

score: 18
Accepted
time: 25ms
memory: 199276kb

input:

38 46

output:

651393374

result:

ok 1 number(s): "651393374"

Test #12:

score: 18
Accepted
time: 23ms
memory: 199152kb

input:

37 39

output:

746919932

result:

ok 1 number(s): "746919932"

Test #13:

score: 18
Accepted
time: 24ms
memory: 199128kb

input:

30 50

output:

214086425

result:

ok 1 number(s): "214086425"

Test #14:

score: 18
Accepted
time: 26ms
memory: 199168kb

input:

50 41

output:

193351204

result:

ok 1 number(s): "193351204"

Test #15:

score: 18
Accepted
time: 22ms
memory: 199120kb

input:

44 32

output:

63855946

result:

ok 1 number(s): "63855946"

Test #16:

score: 18
Accepted
time: 20ms
memory: 199104kb

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: 24ms
memory: 199192kb

input:

199 200

output:

841552647

result:

ok 1 number(s): "841552647"

Test #18:

score: 31
Accepted
time: 22ms
memory: 199156kb

input:

200 200

output:

157842226

result:

ok 1 number(s): "157842226"

Test #19:

score: 31
Accepted
time: 23ms
memory: 199076kb

input:

156 199

output:

216453917

result:

ok 1 number(s): "216453917"

Test #20:

score: 31
Accepted
time: 24ms
memory: 199068kb

input:

161 199

output:

539960909

result:

ok 1 number(s): "539960909"

Test #21:

score: 31
Accepted
time: 26ms
memory: 199072kb

input:

194 160

output:

764024671

result:

ok 1 number(s): "764024671"

Test #22:

score: 31
Accepted
time: 22ms
memory: 199064kb

input:

184 195

output:

117763744

result:

ok 1 number(s): "117763744"

Test #23:

score: 31
Accepted
time: 22ms
memory: 199156kb

input:

152 174

output:

350941677

result:

ok 1 number(s): "350941677"

Test #24:

score: 31
Accepted
time: 23ms
memory: 199124kb

input:

195 186

output:

130526660

result:

ok 1 number(s): "130526660"

Test #25:

score: 31
Accepted
time: 24ms
memory: 199124kb

input:

173 159

output:

754934766

result:

ok 1 number(s): "754934766"

Test #26:

score: 31
Accepted
time: 24ms
memory: 199176kb

input:

194 170

output:

956364877

result:

ok 1 number(s): "956364877"

Subtask #4:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 0
Wrong Answer
time: 62ms
memory: 199172kb

input:

3000 2999

output:

608694239

result:

wrong answer 1st numbers differ - expected: '5195706', found: '608694239'