Submission #1001078

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

template<class T>
T pow(T x, ll n, T r = 1) {
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    static uint normS(const uint &x) {return (x<MD)?x:x-MD;};
    static ModInt make(const uint &x) {ModInt m; m.v = x; return m;}
    ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));}
    ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    static ModInt inv(const ModInt &x) {
        return pow(ModInt(x), MD-2);
    }
};
using Mint = ModInt<TEN(9)+7>;

using T = tuple<int, int, int, int, int>;
map<T, Mint> dp;
int n;
Mint calc(int p, int a, int b, int c, int f) {
    if (p == 2*n) {
        if (f == 0) return 1;
        return 0;
    }
    T key = T(p, a, b, c, f);
    if (dp.count(key)) {
        return dp[key];
    }
    // non use
    Mint ans = 0;
    if ((f & 4) == 0) {
        ans += calc(p+1, a, b, c, (f<<1)+1);
    }
    // back single
    if (a && (f & 1)) {
        ans += calc(p+1, a-1, b, c, (f^1)<<1);
    }
    if (b && (f & 2)) {
        ans += calc(p+1, a, b-1, c, (f^2)<<1);
    }
    if (c && (f & 4)) {
        ans += calc(p+1, a, b, c-1, (f^4)<<1);
    }
    return dp[key] = ans;
}


Mint fact[100000], iFac[100000];
Mint C(int n, int k) {
    return fact[n]*iFac[k]*iFac[n-k];
}
int main() {
    fact[0] = 1;
    for (int i = 1; i < 100000; i++) {
        fact[i] = fact[i-1]*i;
    }
    for (int i = 0; i < 100000; i++) {
        iFac[i] = Mint::inv(fact[i]);
    }

    ios::sync_with_stdio(0);
    cout << setprecision(20);
    cin >> n;
    int a, b, c;
    cin >> a >> b >> c;
    Mint ans = 0;
    for (int x = 0; x <= c; x++) {
        for (int y = 0; y <= c; y++) {
            int z = a-y;
            if (z < 0) continue;
            int nb = b;
            int nc = c-3*x-y;
            if (nc < 0) continue;
            if (nb % 2) continue;
            int w = nb/2;
            Mint base = 1;
            base *= C(x+y+z+w, x);
            base *= C(y+z+w, y);
            base *= C(z+w, z);
            int cu = nc;
            if (cu && w == 0) continue;
            if (cu > 0) {
                base *= C(cu+w-1, cu);
            }
            ans += base;
        }
    }
    cout << ans.v << endl;
    return 0;
}

Submission Info

Judge Result