QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548471#8942. Sugar Sweet 3ucup-team004#AC ✓631ms5264kbC++207.2kb2024-09-05 18:45:352024-09-05 18:45:35

Judging History

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

  • [2024-09-05 18:45:35]
  • 评测
  • 测评结果:AC
  • 用时:631ms
  • 内存:5264kb
  • [2024-09-05 18:45:35]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
// TODO: Dynamic ModInt

template<typename T>
constexpr T power(T a, u64 b) {
    T res {1};
    for (; b != 0; b /= 2, a *= a) {
        if (b % 2 == 1) {
            res *= a;
        }
    }
    return res;
}

template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return 1ULL * a * b % P;
}

template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

template<typename U, U P>
requires std::unsigned_integral<U>
struct ModIntBase {
public:
    constexpr ModIntBase() : x {0} {}
    
    template<typename T>
    requires std::integral<T>
    constexpr ModIntBase(T x_) : x {norm(x_ % T {P})} {}
    
    constexpr static U norm(U x) {
        if ((x >> (8 * sizeof(U) - 1) & 1) == 1) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    
    constexpr U val() const {
        return x;
    }
    
    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = norm(P - x);
        return res;
    }
    
    constexpr ModIntBase inv() const {
        return power(*this, P - 2);
    }
    
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<P>(x, rhs.val());
        return *this;
    }
    
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator!=(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() != rhs.val();
    }
    
    friend constexpr bool operator<(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() < rhs.val();
    }
    
private:
    U x;
};

template<u32 P>
using ModInt = ModIntBase<u32, P>;

template<u64 P>
using ModInt64 = ModIntBase<u64, P>;

constexpr u32 P = 1000000007;
using Z = ModInt<P>;

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int A, B, C, x;
    std::cin >> A >> B >> C >> x;
    
    int S = A + B + C;
    
    if (S % 2 != 0 || std::max({A, B, C}) > S / 2) {
        std::cout << 0 << "\n";
        return 0;
    }
    
    int M = std::max({A, B, C});
    
    std::vector<Z> iw(M + 1);
    for (int i = 0; i <= M; i++) {
        iw[i] = comb.binom(2 * i + 1, i) * comb.inv(2 * i + 1);
    }
    std::vector<Z> w(M + 1);
    w[0] = 1;
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j < i; j++) {
            w[i] -= w[j] * iw[i - j];
        }
    }
    w[0] = 0;
    for (int i = 1; i <= M; i++) {
        w[i] *= -1;
    }
    
    std::vector<Z> y(S / 2 + 1);
    
    std::vector dp(M + 1, std::vector<Z>(M + 1));
    dp[0][0] = 1;
    for (int x = M; x >= 1; x--) {
        for (int i = M; i >= 0; i--) {
            for (int j = i / x; j >= 0; j--) {
                Z pw = 1;
                for (int a = 1; i + a * x <= M; a++) {
                    pw *= w[x];
                    dp[i + a * x][j + a] += dp[i][j] * pw * comb.invfac(a);
                }
            }
        }
    }
    
    std::vector dpy(S / 2 + 1, std::vector<Z>(M + 1));
    for (int x = 0; x <= S / 2; x++) {
        for (int i = 0; i <= M; i++) {
            for (int j = i; j >= 0; j--) {
                dpy[x][i] = dpy[x][i] * x + dp[i][j];
            }
        }
    }
    for (int aa = 0; aa <= A; aa++) {
        for (int bb = 0; bb <= B; bb++) {
            int cc = S / 2 - aa - bb;
            if (cc < 0 || cc > C) {
                continue;
            }
            
            std::vector<Z> f(S / 2 + 1);
            for (int x = 0; x <= S / 2; x++) {
                f[x] = dpy[x][aa] * dpy[x][bb] * dpy[x][cc];
            }
            
            Z sum = 0;
            for (int ab = 0; aa + ab <= A && ab <= bb; ab++) {
                int ac = A - aa - ab;
                int cb = bb - ab;
                int ca = C - cc - cb;
                int ba = aa - ca;
                int bc = B - bb - ba;
                
                if (ac < 0 || cb < 0 || ca < 0 || ba < 0 || bc < 0) {
                    continue;
                }
                
                sum += comb.binom(aa, ba) * comb.binom(bb, cb) * comb.binom(cc, ac);
            }
            
            for (int x = 0; x <= S / 2; x++) {
                y[x] += f[x] * sum;
            }
        }
    }
    
    std::vector<Z> prod(S / 2 + 1), g(S / 2 + 1);
    g[0] = y[0];
    prod[0] = 1;
    for (int i = 1; i <= S / 2; i++) {
        Z cur = 0;
        for (int j = i - 1; j >= 0; j--) {
            prod[j + 1] += prod[j];
            prod[j] *= -(i - 1);
            cur = cur * i + g[j];
        }
        Z w = (y[i] - cur) * comb.invfac(i);
        for (int j = 0; j <= i; j++) {
            g[j] += prod[j] * w;
        }
    }
    
    Z ans = 0;
    for (int i = 0; i <= S / 2; i++) {
        g[i] *= comb.fac(i);
        ans += power(Z(i), x) * g[i];
    }
    std::cout << ans << "\n";
    
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

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

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

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

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 301ms
memory: 4428kb

input:

100 300 400 1515897

output:

279831696

result:

ok 1 number(s): "279831696"

Test #6:

score: 0
Accepted
time: 202ms
memory: 4224kb

input:

120 310 298 1155114

output:

903227392

result:

ok 1 number(s): "903227392"

Test #7:

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

input:

1 1 2 1

output:

18

result:

ok 1 number(s): "18"

Test #8:

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

input:

5 5 10 1919810

output:

696652039

result:

ok 1 number(s): "696652039"

Test #9:

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

input:

1 1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

1 1 798 15154848

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 252ms
memory: 4360kb

input:

1 399 400 1616897

output:

987648925

result:

ok 1 number(s): "987648925"

Test #12:

score: 0
Accepted
time: 254ms
memory: 4348kb

input:

400 398 2 45458123

output:

830387421

result:

ok 1 number(s): "830387421"

Test #13:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

89 75 18 66278

output:

940243796

result:

ok 1 number(s): "940243796"

Test #14:

score: 0
Accepted
time: 471ms
memory: 4440kb

input:

333 333 334 1

output:

60970749

result:

ok 1 number(s): "60970749"

Test #15:

score: 0
Accepted
time: 475ms
memory: 4380kb

input:

334 333 333 1000000000

output:

159064905

result:

ok 1 number(s): "159064905"

Test #16:

score: 0
Accepted
time: 492ms
memory: 5264kb

input:

1 499 500 1515987

output:

880517266

result:

ok 1 number(s): "880517266"

Test #17:

score: 0
Accepted
time: 494ms
memory: 5148kb

input:

500 498 2 1514789

output:

93909141

result:

ok 1 number(s): "93909141"

Test #18:

score: 0
Accepted
time: 631ms
memory: 5172kb

input:

250 250 500 19198877

output:

172243832

result:

ok 1 number(s): "172243832"

Test #19:

score: 0
Accepted
time: 550ms
memory: 4760kb

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