QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722787 | #8942. Sugar Sweet 3 | qL | AC ✓ | 859ms | 7900kb | C++14 | 2.7kb | 2024-11-07 20:11:44 | 2024-11-07 20:11:46 |
Judging History
answer
/*
* @Author: qL
* @Date: 2024-11-06 18:47:17
* @LastEditTime: 2024-11-07 20:10:10
* @Problem: Sugar Sweet 3
* @Link: https://qoj.ac/contest/1780/problem/8942
* @Solution: Official + Local
*/
#include <cstdio>
#include <algorithm>
#define _(func) __builtin_##func
using i32 = int;
using i64 = long long;
constexpr i32 N = 1000;
constexpr i32 mod = 1e9 + 7;
constexpr i64 qpow(i64 x, i32 p) noexcept {
i64 r = 1;
for (; p; p >>= 1, (x *= x) %= mod)
if (p & 1) (r *= x) %= mod;
return r;
}
i32 u, v, w, x, pw[N / 2 + 1], n;
i64 fac[N / 2 + 1], ifac[N / 2 + 1];
i64 binom(i32 n, i32 m) noexcept { return n < m || m < 0 ? 0 : fac[n] * ifac[m] % mod * ifac[n - m] % mod; }
i64 Catalan[N / 2 + 1], f[N / 2 + 1][N / 2 + 1], g[N / 2 + 1][N / 2 + 1], h[N / 2 + 1], p[N / 2 + 1], q[N / 2 + 1];
signed main() noexcept {
scanf("%d%d%d%d", &u, &v, &w, &x), n = (u + v + w);
if (n & 1) return puts("0"), 0;
n /= 2;
fac[0] = 1;
for (i32 i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
ifac[n] = qpow(fac[n], mod - 2);
for (i32 i = n; i; --i) ifac[i - 1] = ifac[i] * i % mod;
for (i32 i = 0; i <= n; ++i) pw[i] = qpow(i, x);
Catalan[0] = 1;
for (i32 i = 1; i <= n; ++i)
for (i32 j = 0; j < i; ++j) (Catalan[i] += Catalan[j] * Catalan[i - j - 1]) %= mod;
f[0][0] = 1;
for (i32 i = 1; i <= n; ++i)
for (i32 j = 1; j <= i; ++j)
for (i32 k = 0; k < i; ++k) (f[i][j] += f[k][j - 1] * Catalan[i - k - 1]) %= mod;
for (i32 i = 0; i <= n; ++i)
for (i32 j = 0; j <= i; ++j) (f[i][j] *= ifac[j]) %= mod;
for (i32 i = 0; i <= n; ++i)
for (i32 x = 0; x <= n; ++x) {
i64 y = 1;
for (i32 j = 0; j <= i; ++j) (g[i][x] += f[i][j] * y) %= mod, (y *= x) %= mod;
}
i64 ans = 0;
for (i32 a = 0; a <= u; ++a) {
for (i32 b = 0; b <= v; ++b) {
i32 c = n - a - b;
if (c < 0) break;
i64 now = 0;
for (i32 i1 = 0; i1 <= v - b; ++i1) {
i32 i2 = w - c - a + i1, i3 = v - b - i1;
(now += binom(a, i1) * binom(b, i2) % mod * binom(c, i3)) %= mod;
}
for (i32 i = 0; i <= n; ++i) (h[i] += g[a][i] * g[b][i] % mod * g[c][i] % mod * now) %= mod;
}
}
q[0] = 1;
for (i32 i = 0; i <= n; ++i)
for (i32 j = i + 1; ~j; --j) q[j] = ((j ? q[j - 1] : 0) + mod - q[j] * i % mod) % mod;
for (i32 i = 0; i <= n; ++i) {
i64 t = 1;
for (i32 j = 0; j <= n; ++j)
if (i != j) (t *= i - j) %= mod;
t = h[i] * qpow(t, mod - 2) % mod;
i64 val = q[n + 1];
for (i32 j = n; ~j; --j) (p[j] += t * val) %= mod, val = (q[j] + val * i) % mod;
}
for (i32 i = 0; i < n; ++i) p[i] < 0 && (p[i] += mod);
for (i32 i = 0; i <= n; ++i) (ans += p[i] * fac[i] % mod * pw[i]) %= mod;
printf("%lld\n", (ans + mod) % mod);
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5996kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 295ms
memory: 7328kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 255ms
memory: 7384kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 1ms
memory: 6032kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 226ms
memory: 7512kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 221ms
memory: 7512kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 439ms
memory: 7360kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 3ms
memory: 6116kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 754ms
memory: 7836kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 755ms
memory: 7708kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 450ms
memory: 7772kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 859ms
memory: 7900kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 610ms
memory: 7720kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 701ms
memory: 7888kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 0ms
memory: 6096kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed