Submission #19426722


Source Code Expand

Copy
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
// #include <atcoder/all>
// using namespace atcoder;
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
using vll = vector<ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
ostream& operator<<(ostream& os, lpair& h){ os << "(" << h.first << ", " << h.second << ")"; return os;}
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
struct Combination{
private:
    ll N;
public:
    vll fac, facinv, inv;

    Combination(ll n){
        N = n;
        fac.resize(N+1); facinv.resize(N+1); inv.resize(N+1);
        fac[0] = fac[1] = 1;
        facinv[0] = facinv[1] = 1;
        inv[1] = 1;
        rep(i,2,N+1){
            fac[i] = fac[i-1] * i % MOD;
            inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
            facinv[i] = facinv[i-1] * inv[i] % MOD;
        }
    }

    ll power(ll x, ll n, ll m = MOD){
        if(n == 0) return 1LL;
        ll res = power(x * x % m, n/2, m);
        if(n % 2 == 1) (res *= x) %= m;
        return res;
    }

    ll nck(ll n, ll k){
        if(k == 0 || n == k) return 1LL;
        if(n < k) return 0LL;
        return fac[n] * facinv[k] % MOD * facinv[n-k] % MOD;
    }
    
    ll npk(ll n, ll k){
        if(k == 0) return 1LL;
        if(n < k) return 0LL;
        return fac[n] * facinv[n-k] % MOD;
    }
};

void solve(){
    vll f(30);
    vll x;
    rep(i,0,26) cin >> f[i];
    rep(i,0,26){
        if(f[i] > 0) x.push_back(f[i]);
    }
    ll N = x.size();
    vector<vll> dp(N+1, vll(300, 0));
    Combination cb(310);

    dp[0][0] = 1;
    vll sum(N+1);
    rep(i,0,N) sum[i+1] = sum[i] + x[i];

    rep(i,0,N){
        rep(j,0,sum[i]+1){
            rep(k,1,x[i]+1){
                rep(l,0,min(k,j)+1){
                    ll p = cb.nck(x[i]-1, k-1);
                    ll p2 = cb.nck(j, l) * cb.nck(sum[i]-j+1, k-l);
                    p *= p2;
                    p %= MOD;
                    ll nxt_j = j - l + (x[i]-k);
                    dp[i+1][nxt_j] += dp[i][j] * p % MOD;
                    dp[i+1][nxt_j] %= MOD;

                }
            }
        }
    }
    print(dp[N][0]);

    

}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}

Submission Info

Submission Time
Task O - 文字列
User yuji9511
Language C++ (GCC 9.2.1)
Score 6
Code Size 2554 Byte
Status AC
Exec Time 10 ms
Memory 3660 KB

Judge Result

Set Name All
Score / Max Score 6 / 6
Status
AC × 4
Set Name Test Cases
All 00, 01, 90, 91
Case Name Status Exec Time Memory
00 AC 10 ms 3604 KB
01 AC 4 ms 3660 KB
90 AC 2 ms 3552 KB
91 AC 2 ms 3588 KB