Submission #3401789


Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;
const long long int MOD = 1000000007;
long long int mod_pow(long long int N, long long int K) {
    long long int ret = 1;
    for(; K>0; K>>=1) {
        if(K & 1) (ret *= N) %= MOD;
        (N *= N) %= MOD;
    }
    return ret;
}
const int MAXN = 1010;

int N, D, sum;
long long int comb[MAXN][MAXN], combA[MAXN], combB[MAXN];
void init_comb() {
    for(int i=0; i<MAXN; i++) {
        comb[i][0] = 1;
        for(int j=1; j<MAXN; j++) {
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
        }
    }
    combA[0] = combB[0] = 1;
    for(int i=1; i<MAXN; i++) {
        combA[i] = combA[i-1] * (D-i+1) % MOD;
        combB[i] = combB[i-1] * mod_pow(i, MOD-2) % MOD;
    }
}

long long int calcComb(int r) {
    return combA[r] * combB[r] % MOD;
}

long long int dp[31][31][31*31], ans;
int main() {
    cin >> N >> D; init_comb();
    dp[0][0][0] = 1;
    for(int i=0; i<N; i++) {
        int val; cin >> val, sum += val;
        for(int j=0; j<=i; j++) {
            for(int k=0; k<sum; k++) {
                (dp[i+1][j][k] += dp[i][j][k]) %= MOD;
                for(int take=0; take<val; take++) {
                    if(k + take >= D) continue;
                    (dp[i+1][j+1][k+take] += dp[i][j][k] * comb[k+take][take]) %= MOD;
                }
            }
        }
    }
    for(int j=0; j<=N; j++) for(int k=0; k<=min(D-1, sum); k++) {
        long long int val = dp[N][j][k];
        // 残っているのは D - k 個
        // これを配置してから、N - j 種類のうちのどれかにする
        (val *= calcComb(k)) %= MOD; // D choose k (D は不変)
        (val *= mod_pow(N - j, D - k)) %= MOD;
        ans = (ans + val * (j % 2 ? -1 : 1) + MOD) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task D - 天下一ボディービルコンテスト
User tsutaj
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1879 Byte
Status WA
Exec Time 40 ms
Memory 13696 KB

Judge Result

Set Name level1 level2 level3
Score / Max Score 0 / 40 0 / 100 0 / 140
Status
AC × 26
WA × 1
AC × 49
WA × 1
AC × 73
WA × 1
Set Name Test Cases
level1 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt
level2 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt, level2_max_0.txt, level2_maxrand_0.txt, level2_maxrand_1.txt, level2_maxrand_2.txt, level2_maxrand_3.txt, level2_maxrand_4.txt, level2_maxrand_5.txt, level2_maxrand_6.txt, level2_maxrand_7.txt, level2_maxrand_8.txt, level2_maxrand_9.txt, level2_min1_0.txt, level2_min2_0.txt, level2_rand_0.txt, level2_rand_1.txt, level2_rand_2.txt, level2_rand_3.txt, level2_rand_4.txt, level2_rand_5.txt, level2_rand_6.txt, level2_rand_7.txt, level2_rand_8.txt, level2_rand_9.txt
level3 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt, level2_max_0.txt, level2_maxrand_0.txt, level2_maxrand_1.txt, level2_maxrand_2.txt, level2_maxrand_3.txt, level2_maxrand_4.txt, level2_maxrand_5.txt, level2_maxrand_6.txt, level2_maxrand_7.txt, level2_maxrand_8.txt, level2_maxrand_9.txt, level2_min1_0.txt, level2_min2_0.txt, level2_rand_0.txt, level2_rand_1.txt, level2_rand_2.txt, level2_rand_3.txt, level2_rand_4.txt, level2_rand_5.txt, level2_rand_6.txt, level2_rand_7.txt, level2_rand_8.txt, level2_rand_9.txt, level3_max_0.txt, level3_maxrand_0.txt, level3_maxrand_1.txt, level3_maxrand_2.txt, level3_maxrand_3.txt, level3_maxrand_4.txt, level3_maxrand_5.txt, level3_maxrand_6.txt, level3_maxrand_7.txt, level3_maxrand_8.txt, level3_maxrand_9.txt, level3_min1_0.txt, level3_min2_0.txt, level3_rand_0.txt, level3_rand_1.txt, level3_rand_2.txt, level3_rand_3.txt, level3_rand_4.txt, level3_rand_5.txt, level3_rand_6.txt, level3_rand_7.txt, level3_rand_8.txt, level3_rand_9.txt, level3_sample3.txt
Case Name Status Exec Time Memory
level1_max_0.txt AC 5 ms 9344 KB
level1_maxrand_0.txt AC 4 ms 9344 KB
level1_maxrand_1.txt AC 5 ms 9344 KB
level1_maxrand_2.txt AC 5 ms 9344 KB
level1_maxrand_3.txt AC 5 ms 9344 KB
level1_maxrand_4.txt AC 4 ms 9344 KB
level1_maxrand_5.txt AC 4 ms 9344 KB
level1_maxrand_6.txt AC 4 ms 9344 KB
level1_maxrand_7.txt AC 5 ms 9344 KB
level1_maxrand_8.txt AC 5 ms 9344 KB
level1_maxrand_9.txt AC 5 ms 9344 KB
level1_min1_0.txt AC 5 ms 9344 KB
level1_min2_0.txt AC 5 ms 9344 KB
level1_min3_0.txt AC 5 ms 9344 KB
level1_min4_0.txt AC 4 ms 9344 KB
level1_rand_0.txt AC 5 ms 9344 KB
level1_rand_1.txt AC 4 ms 9344 KB
level1_rand_2.txt AC 5 ms 9344 KB
level1_rand_3.txt AC 5 ms 9344 KB
level1_rand_4.txt AC 5 ms 9344 KB
level1_rand_5.txt AC 5 ms 9344 KB
level1_rand_6.txt AC 5 ms 9344 KB
level1_rand_7.txt AC 5 ms 9344 KB
level1_rand_8.txt WA 4 ms 9344 KB
level1_rand_9.txt AC 4 ms 9344 KB
level1_sample1.txt AC 4 ms 9344 KB
level1_sample2.txt AC 5 ms 9344 KB
level2_max_0.txt AC 5 ms 9344 KB
level2_maxrand_0.txt AC 4 ms 9344 KB
level2_maxrand_1.txt AC 4 ms 9344 KB
level2_maxrand_2.txt AC 5 ms 9344 KB
level2_maxrand_3.txt AC 5 ms 9344 KB
level2_maxrand_4.txt AC 4 ms 9344 KB
level2_maxrand_5.txt AC 5 ms 9344 KB
level2_maxrand_6.txt AC 5 ms 9344 KB
level2_maxrand_7.txt AC 5 ms 9344 KB
level2_maxrand_8.txt AC 5 ms 9344 KB
level2_maxrand_9.txt AC 5 ms 9344 KB
level2_min1_0.txt AC 5 ms 9344 KB
level2_min2_0.txt AC 5 ms 9344 KB
level2_rand_0.txt AC 5 ms 9344 KB
level2_rand_1.txt AC 5 ms 9344 KB
level2_rand_2.txt AC 5 ms 9344 KB
level2_rand_3.txt AC 5 ms 9344 KB
level2_rand_4.txt AC 5 ms 9344 KB
level2_rand_5.txt AC 4 ms 9344 KB
level2_rand_6.txt AC 5 ms 9344 KB
level2_rand_7.txt AC 4 ms 9344 KB
level2_rand_8.txt AC 4 ms 9344 KB
level2_rand_9.txt AC 4 ms 9344 KB
level3_max_0.txt AC 40 ms 13696 KB
level3_maxrand_0.txt AC 15 ms 13568 KB
level3_maxrand_1.txt AC 13 ms 13568 KB
level3_maxrand_2.txt AC 13 ms 13568 KB
level3_maxrand_3.txt AC 15 ms 13568 KB
level3_maxrand_4.txt AC 13 ms 13568 KB
level3_maxrand_5.txt AC 17 ms 13568 KB
level3_maxrand_6.txt AC 16 ms 13568 KB
level3_maxrand_7.txt AC 14 ms 13568 KB
level3_maxrand_8.txt AC 15 ms 13568 KB
level3_maxrand_9.txt AC 13 ms 13568 KB
level3_min1_0.txt AC 6 ms 13568 KB
level3_min2_0.txt AC 5 ms 9344 KB
level3_rand_0.txt AC 10 ms 13568 KB
level3_rand_1.txt AC 9 ms 13568 KB
level3_rand_2.txt AC 5 ms 9344 KB
level3_rand_3.txt AC 7 ms 11520 KB
level3_rand_4.txt AC 5 ms 9344 KB
level3_rand_5.txt AC 7 ms 11520 KB
level3_rand_6.txt AC 7 ms 11520 KB
level3_rand_7.txt AC 8 ms 13568 KB
level3_rand_8.txt AC 6 ms 11520 KB
level3_rand_9.txt AC 5 ms 9472 KB
level3_sample3.txt AC 5 ms 11520 KB