提出 #26997523

---

ソースコード 拡げる

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 1000000007
#define maxn 1010
#define maxm 22

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b;
ll dp[maxm][maxn], fc[maxn], nv[maxn], x;

ll fxp(ll b, ll e) {
    ll r = 1, k = b;
    while (e != 0) {
        if (e % 2) r = (r * k) % mod;
        k = (k * k) % mod; e /= 2;
    }
    return r;
}

ll inv(ll x) {
    return fxp(x, mod - 2);
}

ll bnm(ll a, ll b) {
    if (a < b || b < 0) return 0;
    ll r = (fc[a] * nv[b]) % mod;
    r = (r * nv[a - b]) % mod;
    return r;
}

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

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    fc[0] = 1; nv[0] = 1;
    for (i = 1; i < maxn; i++) {
        fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]);
    }

    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> a[i];
    }

    dp[0][0] = 1;
    for (i = 1; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            for (k = 0; k <= min(j, a[i]); k++) {
                x = (dp[i - 1][j - k] * bnm(n - j + k, k)) % mod;
                x = (x * bnm(n - k, a[i] - k)) % mod;
                dp[i][j] = (dp[i][j] + x) % mod;
            }
        }
    }

    cout << dp[m][n] << nl;

    return 0;
}

提出情報

ジャッジ結果