QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#756152 | #8942. Sugar Sweet 3 | dalao_see_me | AC ✓ | 1365ms | 9604kb | C++14 | 3.3kb | 2024-11-16 19:10:53 | 2024-11-16 19:10:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
return x * f;
}
int quickpow(int a, int b, int mod) {
int res = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod)
if (b & 1) res = 1LL * res * a % mod;
return res;
}
const int N = 1005, mod = 1e9 + 7;
int a, b, c, x, m, n, ans;
int f[N][N], fac[N], Inv[N], inv[N], F[N][N], G[N], g[N], h[N];
void mul(int *f, int c) {
for (int i = 0; i <= m; i++) f[i] = 1LL * f[i] * c % mod;
}
void mull(int *f, int p) {
for (int i = m + 1; ~i; i--) {
f[i] = 1LL * f[i] * p % mod;
if (i) f[i] = (f[i] + f[i - 1]) % mod;
}
}
void divv(int *f, int p) {
for (int i = 0; i <= m + 1; i++) {
if (i) f[i] = (f[i] - f[i - 1] + mod) % mod;
f[i] = 1LL * f[i] * p % mod;
}
}
int C(int a, int b) {
if (a < 0 || b < 0 || a < b) return 0;
return 1LL * fac[a] * Inv[b] % mod * Inv[a - b] % mod;
}
void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
void Solve() {
a = read(); b = read(); c = read(); x = read(); n = a + b + c;
if (n & 1) return void(puts("0")); m = n >> 1;
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % mod;
Inv[n] = quickpow(fac[n], mod - 2, mod);
for (int i = n - 1; ~i; i--) Inv[i] = 1LL * Inv[i + 1] * (i + 1) % mod;
for (int i = 1; i <= n; i++) inv[i] = 1LL * Inv[i] * fac[i - 1] % mod;
f[0][0] = 1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < i; k++)
f[i][j] = (f[i][j] + 1LL * f[i - k - 1][j - 1] * (C(k * 2, k) - C(k * 2, k + 1) + mod)) % mod;
for (int u = 0; u <= m; u++)
for (int x = 0; x <= m; x++) {
int s = 1;
for (int i = 0; i <= m; i++) {
F[u][x] = (F[u][x] + 1LL * f[u][i] * s % mod * Inv[i]) % mod;
s = 1LL * s * x % mod;
}
}
for (int u = 0; u <= min(a, m); u++)
for (int v = 0; v <= b && u + v <= m; v++) {
int w = m - u - v, res = 0;
for (int xb = 0; xb <= a - u; xb++) {
int xc = a - u - xb, zb = v - xb, za = c - w - zb, ya = u - za, yc = b - v - ya;
if (xb < 0 || xc < 0 || ya < 0 || yc < 0 || za < 0 || zb < 0) continue;
res = (res + 1LL * C(u, ya) * C(v, zb) % mod * C(w, xc)) % mod;
}
for (int i = 0; i <= m; i++) G[i] = (G[i] + 1LL * F[u][i] * F[v][i] % mod * F[w][i] % mod * res) % mod;
}
h[0] = 1;
for (int i = 1; i <= m; i++) mull(h, (mod - i) % mod);
for (int i = 0; i <= m; i++) {
if (i) divv(h, (mod - inv[i]) % mod);
int t = 1LL * Inv[i] * Inv[m - i] % mod * G[i] % mod;
if ((m - i) & 1) t = (mod - t) % mod;
for (int j = 0; j <= m; j++) g[j] = (g[j] + 1LL * h[j] * t) % mod;
mull(h, (mod - i) % mod);
}
for (int i = 0; i <= m; i++) ans = (ans + 1LL * g[i] * quickpow(i, x, mod) % mod * fac[i]) % mod;
printf("%d\n", ans);
}
int main() {
int _ = 1;
while (_--) Solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5904kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5988kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 608ms
memory: 7560kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 485ms
memory: 7764kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5904kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5932kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 560ms
memory: 8208kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 557ms
memory: 7456kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 699ms
memory: 8340kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 6ms
memory: 6308kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 1350ms
memory: 9604kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 1336ms
memory: 8052kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 1093ms
memory: 8204kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 1365ms
memory: 8328kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 1226ms
memory: 8212kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 1310ms
memory: 9268kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed