QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#667274#8942. Sugar Sweet 3ucup-team173WA 557ms4904kbC++234.3kb2024-10-22 22:00:182024-10-22 22:00:26

Judging History

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

  • [2024-10-22 22:00:26]
  • 评测
  • 测评结果:WA
  • 用时:557ms
  • 内存:4904kb
  • [2024-10-22 22:00:18]
  • 提交

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] + 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 557ms
memory: 4904kb

input:

100 300 400 1515897

output:

143578295

result:

wrong answer 1st numbers differ - expected: '279831696', found: '143578295'