QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#667274 | #8942. Sugar Sweet 3 | ucup-team173 | WA | 557ms | 4904kb | C++23 | 4.3kb | 2024-10-22 22:00:18 | 2024-10-22 22:00:26 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int Mod = 1e9 + 7;
typedef vector<int> Poly;
// Poly operator * (Poly a, Poly b) {
// Poly c((int)a.size() + (int)b.size() - 1);
// for (int i = 0; i < a.size(); i++) {
// for (int j = 0; j < b.size(); j++) {
// c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % Mod;
// }
// }
// return c;
// }
void solve() {
int A, B, C, x;
cin >> A >> B >> C >> x;
int n = A + B + C;
if (n & 1) {
cout << 0;
return ;
}
vector<int> ifac(n + 1), fac(n + 1);
auto fpow = [&](int x, int k) {
int ans = 1;
for (; k; k >>= 1, x = 1ll * x * x % Mod) {
if (k & 1) ans = 1ll * ans * x % Mod;
}
return ans;
};
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = 1ll * fac[i - 1] * i % Mod;
}
ifac[n] = fpow(fac[n], Mod - 2);
for (int i = n; i >= 1; i--) {
ifac[i - 1] = 1ll * ifac[i] * i % Mod;
}
auto binom = [&](int n, int m) -> int {
if (m > n || m < 0) return 0;
return 1ll * fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
};
auto catalan = [&](int n) {
return (binom(2 * n, n) - binom(2 * n, n - 1) + Mod) % Mod;
};
// cerr << "aa\n";
vector f((n >> 1) + 1, vector<int>((n >> 1) + 1));
f[0][0] = 1;
for (int i = 1; i <= (n >> 1); i++) {
for (int j = 1; j <= i; j++) {
for (int k = 1; k <= i; k++) {
f[i][j] = (f[i][j] + f[i - k][j - 1] * catalan(k - 1)) % Mod;
}
// cout << f[i][j] << " \n"[j == i];
}
}
// cerr << "tt" << '\n';
vector fval((n >> 1) + 1, vector<int>((n >> 1) + 1));
for (int i = 0; i <= (n >> 1); i++) {
for (int k = 0; k <= (n >> 1); k++) {
for (int j = i; j >= 0; j--) {
fval[i][k] = (1ll * fval[i][k] * k % Mod + 1ll * f[i][j] * ifac[j] % Mod) % Mod;
}
// cerr << fval[i][k] << " \n"[k == (n >> 1)];
}
}
vector val((n >> 1) + 1, 0);
for (int a = 0; a <= A; a++) {
for (int b = 0; b <= B; b++) {
int c = (n >> 1) - a - b;
if (c <= C && c >= 0) {
int cnt = 0;
for (int tab = 0; tab <= min(A - a, b); tab++) {
int tbc = c - ((A - a) - tab);
int tca = a - ((B - b) - tbc);
if (tbc >= 0 && tbc <= B - b && tca >= 0 && tca <= C - c) {
// cnt++;
cnt = (cnt + 1ll * binom(b, tab) * binom(c, tbc) % Mod * binom(a, tca)) % Mod;
}
}
// cerr << a << ' ' << b << ' ' << c << ' ' << cnt << '\n';
for (int k = 0; k <= (n >> 1); k++) {
val[k] = (val[k] + 1ll * fval[a][k] * fval[b][k] % Mod * fval[c][k] % Mod * cnt) % Mod;
}
}
}
}
// for (auto o : val) cerr << o << ' ';
// cerr << '\n';
vector<int> res((n >> 1) + 1);
for (int k = 0; k <= (n >> 1); k++) {
vector<int> mul(1, 1);
for (int i = 0; i <= (n >> 1); i++) if (i != k) {
mul.push_back(0);
for (int j = (int)mul.size() - 1; j >= 0; j--) {
mul[j] = ((j ? mul[j - 1] : 0) - 1ll * mul[j] * i % Mod + Mod) % Mod;
}
}
// cerr << k << "a\n";
// for (auto o : mul) cerr << o << ' ';
// cerr << "bbb\n";
int t = val[k];
for (int i = 0; i <= (n >> 1); i++) if (i != k) {
t = 1ll * t * fpow((k - i + Mod) % Mod, Mod - 2) % Mod;
}
// cerr << t << '\n';
for (int i = 0; i <= (n >> 1); i++) {
res[i] = (res[i] + 1ll * t * mul[i] % Mod) % Mod;
}
}
int ans = 0;
for (int i = 1; i <= (n >> 1); i++) {
ans = (ans + 1ll * fpow(i, x) * res[i] % Mod * fac[i]) % Mod;
}
cout << ans << '\n';
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: -100
Wrong Answer
time: 557ms
memory: 4904kb
input:
100 300 400 1515897
output:
143578295
result:
wrong answer 1st numbers differ - expected: '279831696', found: '143578295'