QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#857702 | #8728. Tablica | GGapaggl | 100 ✓ | 788ms | 19388kb | C++14 | 2.0kb | 2025-01-15 23:38:44 | 2025-01-15 23:38:45 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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