QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#667280 | #8942. Sugar Sweet 3 | ucup-team173 | AC ✓ | 1226ms | 5576kb | C++23 | 4.3kb | 2024-10-22 22:01:48 | 2024-10-22 22:01:57 |
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] + 1ll * 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;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 568ms
memory: 4844kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 452ms
memory: 4640kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 520ms
memory: 5008kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 522ms
memory: 5076kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 523ms
memory: 4792kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 8ms
memory: 3652kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 1222ms
memory: 5508kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 1226ms
memory: 5512kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 1010ms
memory: 5516kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 1012ms
memory: 5492kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 1130ms
memory: 5576kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 1212ms
memory: 5572kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed