QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#667280#8942. Sugar Sweet 3ucup-team173AC ✓1226ms5576kbC++234.3kb2024-10-22 22:01:482024-10-22 22:01:57

Judging History

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

  • [2024-10-22 22:01:57]
  • 评测
  • 测评结果:AC
  • 用时:1226ms
  • 内存:5576kb
  • [2024-10-22 22:01:48]
  • 提交

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