verify/aoj_other/aoj_2751.test.cpp

View this file on GitHub
Last update: 2023-05-31 02:53:46+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2751

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2751"

#include "icpc/template.hpp"
#include "icpc/modint.hpp"
#include "icpc/binomal.hpp"

using fp = Modint<1000000007>;

void solve(long long A, long long B, long long C, long long Sx, long long Sy, Binomial<fp>& binom) {
    fp ans = 0;
    long long d = Sx - Sy;
    long long n = A + B + C;
    for (long long x = max(0LL, d); x <= Sx; x++) {
        long long y = x - d;
        long long s = Sx - x;
        if (x < A or y < B or s < 0) continue;
        if (A == 0 and x > 0) continue;
        if (B == 0 and y > 0) continue;
        fp cur = binom.C(s + n - 1, n - 1);
        if (A != 0) cur *= binom.C(x - 1, A - 1);
        if (B != 0) cur *= binom.C(y - 1, B - 1);
        ans += cur;
    }
    ans *= binom.C(n, A) * binom.C(n - A, B);
    cout << ans << '\n';
}

int main() {
    Binomial<fp> binom(4000000);
    long long A, B, C, Sx, Sy;
    while (cin >> A >> B >> C >> Sx >> Sy, !(A == 0 and B == 0 and C == 0 and Sx == 0 and Sy == 0)) {
        solve(A, B, C, Sx, Sy, binom);
    }
    return 0;
}

#line 1 "verify/aoj_other/aoj_2751.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2751"

#line 2 "icpc/template.hpp"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[ ";
    for (auto& vi : v) os << vi << ", ";
    return os << "]";
}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif

using uint = unsigned int;
using ull = unsigned long long;

// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 2 "icpc/modint.hpp"

#line 4 "icpc/modint.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/3331
// https://onlinejudge.u-aizu.ac.jp/problems/2751

template <uint MD> struct Modint {
    using M = Modint;
    const static M G;
    uint v;
    Modint(ll val = 0) { set_v(val % MD + MD); }
    M& set_v(uint val) {
        v = (val < MD) ? val : val - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
// using mint = Modint<998244353>;
// template<> const mint mint::G = mint(3);
#line 2 "icpc/binomal.hpp"

#line 4 "icpc/binomal.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/2751

template <class T> struct Binomial {
    V<T> f, g;

    Binomial(const int n = 0) {
        f.resize(n);
        g.resize(n);
        f[0] = g[0] = 1;
        for (int i = 1; i < n; i++) f[i] = f[i - 1] * T(i);
        g[n - 1] = T(1) / f[n - 1];
        for (int i = n - 2; i >= 1; i--) g[i] = g[i + 1] * T(i + 1);
    }

    T C(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        return f[N] * g[N - K] * g[K];
    }

    T P(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        return f[N] * g[N - K];
    }

    T C_naive(int N, int K) {
        if (N < 0 or K < 0 or N < K) return 0;
        T res(1);
        K = min(K, N - K);
        for (int i = 1; i <= K; i++) {
            res *= N--;
            res /= i;
        }
        return res;
    }
};
#line 6 "verify/aoj_other/aoj_2751.test.cpp"

using fp = Modint<1000000007>;

void solve(long long A, long long B, long long C, long long Sx, long long Sy, Binomial<fp>& binom) {
    fp ans = 0;
    long long d = Sx - Sy;
    long long n = A + B + C;
    for (long long x = max(0LL, d); x <= Sx; x++) {
        long long y = x - d;
        long long s = Sx - x;
        if (x < A or y < B or s < 0) continue;
        if (A == 0 and x > 0) continue;
        if (B == 0 and y > 0) continue;
        fp cur = binom.C(s + n - 1, n - 1);
        if (A != 0) cur *= binom.C(x - 1, A - 1);
        if (B != 0) cur *= binom.C(y - 1, B - 1);
        ans += cur;
    }
    ans *= binom.C(n, A) * binom.C(n - A, B);
    cout << ans << '\n';
}

int main() {
    Binomial<fp> binom(4000000);
    long long A, B, C, Sx, Sy;
    while (cin >> A >> B >> C >> Sx >> Sy, !(A == 0 and B == 0 and C == 0 and Sx == 0 and Sy == 0)) {
        solve(A, B, C, Sx, Sy, binom);
    }
    return 0;
}