QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#930586 | #8728. Tablica | Cyanmond | 59 | 62ms | 199304kb | C++23 | 2.1kb | 2025-03-10 00:42:16 | 2025-03-10 00:42:24 |
Judging History
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'