QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#857702#8728. TablicaGGapaggl100 ✓788ms19388kbC++142.0kb2025-01-15 23:38:442025-01-15 23:38:45

Judging History

你现在查看的是最新测评结果

  • [2025-01-15 23:38:45]
  • 评测
  • 测评结果:100
  • 用时:788ms
  • 内存:19388kb
  • [2025-01-15 23:38:44]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwrh = (b); i <= stOwrh; i++)
#define per(i, a, b) for(int i = (a), stOwrh = (b); i >= stOwrh; i--)
using namespace std;
using LL = long long;
using VI = vector<int>;

constexpr int mod = 1e9 + 7;

namespace pre {
    constexpr LL qpow(LL x, LL y){
        LL ret = 1;
        for(; y; y >>= 1) {
            if(y & 1) (ret = ret * x % mod);
            (x = x * x % mod) ;
        }
        return ret;
    }

    constexpr LL inv(LL x) {return qpow(x, mod - 2); }
}   
using namespace pre;

namespace binom {
    constexpr int N = 1e6 + 5;
    LL fac[N], iv[N];
 
    void init() {
        fac[0] = 1;
        rep(i, 1, N - 1) fac[i] = fac[i - 1] * i % mod;
        iv[N - 1] = inv(fac[N - 1]); 
        per(i, N - 2, 0) iv[i] = iv[i + 1] * (i + 1) % mod;
    }
 
    LL C(int y, int x) {
        if(x < 0 || y < 0 || y - x < 0) return 0;
        return fac[y] * iv[x] % mod * iv[y - x] % mod;
    }   
}
using binom::C; 
using binom::fac;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    binom::init();

    int n, m; cin >> n >> m;
    
    LL ans = 0;
    rep(a, 0, n) {
        int b, c, d; 
        b = n - a;
        d = a + b * 2 - m; 
        c = m - d;
        // cerr << a << " " << b << " " << c << " " << d << '\n';
        if(c < 0 || d < 0 || a + 2 * b != c + 2 * d) continue;
         
        LL res = 0;
        rep(k, 0, min(b, d)) {
            LL tp = (k & 1 ? mod - 1 : 1);
            (tp *= C(b, k) * C(d, k) % mod * fac[k] % mod) %= mod;
            (tp *= fac[c + 2 * d - k * 2]) %= mod;
            (tp *= inv(qpow(2, b + d - k)) % mod) %= mod;
            (res += tp) %= mod;
        }
        (ans += C(n, a) * C(m, c) % mod * res % mod) %= mod;
        // c + 2d == a + 2b  c + d = m 
    }

    cout << ans << '\n';

    return 0;
}
/*
0 2 0 2
1 1 1 1
2 0 2 0
*/
/*
500000005
1000000006
500000004
500000005
500000003
2
*/

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 11ms
memory: 19340kb

input:

5 6

output:

456750

result:

ok 1 number(s): "456750"

Test #2:

score: 10
Accepted
time: 9ms
memory: 19248kb

input:

6 6

output:

5464710

result:

ok 1 number(s): "5464710"

Test #3:

score: 10
Accepted
time: 9ms
memory: 19320kb

input:

3 5

output:

270

result:

ok 1 number(s): "270"

Test #4:

score: 10
Accepted
time: 10ms
memory: 19372kb

input:

3 6

output:

90

result:

ok 1 number(s): "90"

Test #5:

score: 10
Accepted
time: 10ms
memory: 19224kb

input:

4 6

output:

14580

result:

ok 1 number(s): "14580"

Test #6:

score: 10
Accepted
time: 8ms
memory: 19220kb

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: 8ms
memory: 19188kb

input:

50 49

output:

750700714

result:

ok 1 number(s): "750700714"

Test #8:

score: 18
Accepted
time: 8ms
memory: 19264kb

input:

50 50

output:

630532893

result:

ok 1 number(s): "630532893"

Test #9:

score: 18
Accepted
time: 11ms
memory: 19304kb

input:

41 34

output:

800856205

result:

ok 1 number(s): "800856205"

Test #10:

score: 18
Accepted
time: 10ms
memory: 19228kb

input:

39 41

output:

541550932

result:

ok 1 number(s): "541550932"

Test #11:

score: 18
Accepted
time: 10ms
memory: 19216kb

input:

38 46

output:

651393374

result:

ok 1 number(s): "651393374"

Test #12:

score: 18
Accepted
time: 12ms
memory: 19208kb

input:

37 39

output:

746919932

result:

ok 1 number(s): "746919932"

Test #13:

score: 18
Accepted
time: 7ms
memory: 19304kb

input:

30 50

output:

214086425

result:

ok 1 number(s): "214086425"

Test #14:

score: 18
Accepted
time: 9ms
memory: 19284kb

input:

50 41

output:

193351204

result:

ok 1 number(s): "193351204"

Test #15:

score: 18
Accepted
time: 9ms
memory: 19196kb

input:

44 32

output:

63855946

result:

ok 1 number(s): "63855946"

Test #16:

score: 18
Accepted
time: 8ms
memory: 19236kb

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: 11ms
memory: 19224kb

input:

199 200

output:

841552647

result:

ok 1 number(s): "841552647"

Test #18:

score: 31
Accepted
time: 10ms
memory: 19284kb

input:

200 200

output:

157842226

result:

ok 1 number(s): "157842226"

Test #19:

score: 31
Accepted
time: 10ms
memory: 19216kb

input:

156 199

output:

216453917

result:

ok 1 number(s): "216453917"

Test #20:

score: 31
Accepted
time: 8ms
memory: 19328kb

input:

161 199

output:

539960909

result:

ok 1 number(s): "539960909"

Test #21:

score: 31
Accepted
time: 9ms
memory: 19184kb

input:

194 160

output:

764024671

result:

ok 1 number(s): "764024671"

Test #22:

score: 31
Accepted
time: 13ms
memory: 19388kb

input:

184 195

output:

117763744

result:

ok 1 number(s): "117763744"

Test #23:

score: 31
Accepted
time: 11ms
memory: 19340kb

input:

152 174

output:

350941677

result:

ok 1 number(s): "350941677"

Test #24:

score: 31
Accepted
time: 14ms
memory: 19244kb

input:

195 186

output:

130526660

result:

ok 1 number(s): "130526660"

Test #25:

score: 31
Accepted
time: 9ms
memory: 19336kb

input:

173 159

output:

754934766

result:

ok 1 number(s): "754934766"

Test #26:

score: 31
Accepted
time: 12ms
memory: 19200kb

input:

194 170

output:

956364877

result:

ok 1 number(s): "956364877"

Subtask #4:

score: 41
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 41
Accepted
time: 788ms
memory: 19192kb

input:

3000 2999

output:

5195706

result:

ok 1 number(s): "5195706"

Test #28:

score: 41
Accepted
time: 787ms
memory: 19096kb

input:

3000 3000

output:

224347336

result:

ok 1 number(s): "224347336"

Test #29:

score: 41
Accepted
time: 714ms
memory: 19200kb

input:

2854 2864

output:

513408195

result:

ok 1 number(s): "513408195"

Test #30:

score: 41
Accepted
time: 648ms
memory: 19232kb

input:

2887 2803

output:

58832696

result:

ok 1 number(s): "58832696"

Test #31:

score: 41
Accepted
time: 634ms
memory: 19240kb

input:

2800 2925

output:

804387597

result:

ok 1 number(s): "804387597"

Test #32:

score: 41
Accepted
time: 680ms
memory: 19204kb

input:

2842 2813

output:

971828715

result:

ok 1 number(s): "971828715"

Test #33:

score: 41
Accepted
time: 612ms
memory: 19124kb

input:

2808 2972

output:

329457042

result:

ok 1 number(s): "329457042"

Test #34:

score: 41
Accepted
time: 682ms
memory: 19248kb

input:

2821 2853

output:

81282690

result:

ok 1 number(s): "81282690"

Test #35:

score: 41
Accepted
time: 683ms
memory: 19264kb

input:

2875 2956

output:

105351485

result:

ok 1 number(s): "105351485"

Test #36:

score: 41
Accepted
time: 701ms
memory: 19304kb

input:

2879 2852

output:

672034506

result:

ok 1 number(s): "672034506"

Extra Test:

score: 0
Extra Test Passed