QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497741 | #8728. Tablica | green_gold_dog# | 100 ✓ | 86ms | 4148kb | C++20 | 2.3kb | 2024-07-29 16:54:44 | 2024-07-29 16:54:44 |
Judging History
answer
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, MAXN = 10'000;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
ll binpow(ll a, ll b) {
return (b == 0 ? 1 : square(binpow(a, b / 2)) % MOD * (b % 2 ? a : 1) % MOD);
}
ll inv(ll x) {
return binpow(x, MOD - 2);
}
ll f[MAXN], invf[MAXN], p2[MAXN], invp2[MAXN];
void precalc() {
f[0] = 1;
p2[0] = 1;
invp2[0] = 1;
ll i2 = inv(2);
for (ll i = 1; i < MAXN; i++) {
f[i] = f[i - 1] * i % MOD;
p2[i] = p2[i - 1] * 2 % MOD;
invp2[i] = invp2[i - 1] * i2 % MOD;
}
invf[MAXN - 1] = inv(f[MAXN - 1]);
for (ll i = MAXN - 1; i > 0; i--) {
invf[i - 1] = invf[i] * i % MOD;
}
}
ll C(ll n, ll k) {
if (k > n) {
return 0;
}
return f[n] * invf[k] % MOD * invf[n - k] % MOD;
}
void solve() {
ll n, m;
cin >> n >> m;
if (n > m) {
swap(n, m);
}
ll ans = 0;
for (ll add = m - n; add <= n; add++) {
ll r1 = n - add, r2 = add;
ll c1 = m - (add + n - m), c2 = add + n - m;
ll mul = 1;
ll now = 0;
for (ll col = 0; col <= c2; col++) {
now += C(n, r2) * C(m, c2) % MOD * C(c2, col) % MOD * C(r2, col) % MOD * f[col] % MOD * p2[col] % MOD * f[r1 + r2 * 2 - col * 2] % MOD * mul;
now += MOD;
now %= MOD;
mul *= -1;
}
ans += now * invp2[r2] % MOD * invp2[c2] % MOD;
ans %= MOD;
}
cout << ans << '\n';
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
precalc();
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
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: 3848kb
input:
5 6
output:
456750
result:
ok 1 number(s): "456750"
Test #2:
score: 10
Accepted
time: 1ms
memory: 3848kb
input:
6 6
output:
5464710
result:
ok 1 number(s): "5464710"
Test #3:
score: 10
Accepted
time: 1ms
memory: 3860kb
input:
3 5
output:
270
result:
ok 1 number(s): "270"
Test #4:
score: 10
Accepted
time: 1ms
memory: 3800kb
input:
3 6
output:
90
result:
ok 1 number(s): "90"
Test #5:
score: 10
Accepted
time: 1ms
memory: 3868kb
input:
4 6
output:
14580
result:
ok 1 number(s): "14580"
Test #6:
score: 10
Accepted
time: 1ms
memory: 3920kb
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: 1ms
memory: 4144kb
input:
50 49
output:
750700714
result:
ok 1 number(s): "750700714"
Test #8:
score: 18
Accepted
time: 1ms
memory: 3860kb
input:
50 50
output:
630532893
result:
ok 1 number(s): "630532893"
Test #9:
score: 18
Accepted
time: 1ms
memory: 3848kb
input:
41 34
output:
800856205
result:
ok 1 number(s): "800856205"
Test #10:
score: 18
Accepted
time: 1ms
memory: 3864kb
input:
39 41
output:
541550932
result:
ok 1 number(s): "541550932"
Test #11:
score: 18
Accepted
time: 1ms
memory: 3848kb
input:
38 46
output:
651393374
result:
ok 1 number(s): "651393374"
Test #12:
score: 18
Accepted
time: 1ms
memory: 4144kb
input:
37 39
output:
746919932
result:
ok 1 number(s): "746919932"
Test #13:
score: 18
Accepted
time: 1ms
memory: 3916kb
input:
30 50
output:
214086425
result:
ok 1 number(s): "214086425"
Test #14:
score: 18
Accepted
time: 1ms
memory: 4096kb
input:
50 41
output:
193351204
result:
ok 1 number(s): "193351204"
Test #15:
score: 18
Accepted
time: 1ms
memory: 3848kb
input:
44 32
output:
63855946
result:
ok 1 number(s): "63855946"
Test #16:
score: 18
Accepted
time: 1ms
memory: 3856kb
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: 1ms
memory: 4148kb
input:
199 200
output:
841552647
result:
ok 1 number(s): "841552647"
Test #18:
score: 31
Accepted
time: 0ms
memory: 3856kb
input:
200 200
output:
157842226
result:
ok 1 number(s): "157842226"
Test #19:
score: 31
Accepted
time: 1ms
memory: 3932kb
input:
156 199
output:
216453917
result:
ok 1 number(s): "216453917"
Test #20:
score: 31
Accepted
time: 1ms
memory: 4072kb
input:
161 199
output:
539960909
result:
ok 1 number(s): "539960909"
Test #21:
score: 31
Accepted
time: 1ms
memory: 3844kb
input:
194 160
output:
764024671
result:
ok 1 number(s): "764024671"
Test #22:
score: 31
Accepted
time: 1ms
memory: 3916kb
input:
184 195
output:
117763744
result:
ok 1 number(s): "117763744"
Test #23:
score: 31
Accepted
time: 1ms
memory: 3908kb
input:
152 174
output:
350941677
result:
ok 1 number(s): "350941677"
Test #24:
score: 31
Accepted
time: 0ms
memory: 4144kb
input:
195 186
output:
130526660
result:
ok 1 number(s): "130526660"
Test #25:
score: 31
Accepted
time: 1ms
memory: 4148kb
input:
173 159
output:
754934766
result:
ok 1 number(s): "754934766"
Test #26:
score: 31
Accepted
time: 1ms
memory: 3796kb
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: 86ms
memory: 4132kb
input:
3000 2999
output:
5195706
result:
ok 1 number(s): "5195706"
Test #28:
score: 41
Accepted
time: 86ms
memory: 3868kb
input:
3000 3000
output:
224347336
result:
ok 1 number(s): "224347336"
Test #29:
score: 41
Accepted
time: 77ms
memory: 3932kb
input:
2854 2864
output:
513408195
result:
ok 1 number(s): "513408195"
Test #30:
score: 41
Accepted
time: 71ms
memory: 3844kb
input:
2887 2803
output:
58832696
result:
ok 1 number(s): "58832696"
Test #31:
score: 41
Accepted
time: 68ms
memory: 3936kb
input:
2800 2925
output:
804387597
result:
ok 1 number(s): "804387597"
Test #32:
score: 41
Accepted
time: 74ms
memory: 3848kb
input:
2842 2813
output:
971828715
result:
ok 1 number(s): "971828715"
Test #33:
score: 41
Accepted
time: 67ms
memory: 3912kb
input:
2808 2972
output:
329457042
result:
ok 1 number(s): "329457042"
Test #34:
score: 41
Accepted
time: 74ms
memory: 3848kb
input:
2821 2853
output:
81282690
result:
ok 1 number(s): "81282690"
Test #35:
score: 41
Accepted
time: 75ms
memory: 4072kb
input:
2875 2956
output:
105351485
result:
ok 1 number(s): "105351485"
Test #36:
score: 41
Accepted
time: 76ms
memory: 3916kb
input:
2879 2852
output:
672034506
result:
ok 1 number(s): "672034506"
Extra Test:
score: 0
Extra Test Passed