QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#756152#8942. Sugar Sweet 3dalao_see_meAC ✓1365ms9604kbC++143.3kb2024-11-16 19:10:532024-11-16 19:10:54

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 19:10:54]
  • 评测
  • 测评结果:AC
  • 用时:1365ms
  • 内存:9604kb
  • [2024-11-16 19:10:53]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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