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 |
|
|
|
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 |