第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution
問題
$ N人います。以下の操作を$ K回行います。
$ i回目にはランダムに$ a_i人を選び1つずつクッキーを配ります
最終的に$ i人目が持っているクッキーの数を$ c_iとしたとき、
$ \prod_{i=0}^{N-1} c_iの期待値に$ \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K}をかけたものはいくつでしょう? 考察
積をそのまま考えるのは難しいので、各人が持っているクッキーから1つずつ選ぶ選び方と言い換えます。
各人がもっているクッキーから1つずつ選んだときの、1つの選び方は
人$ iの$ j日目の状況$ x_{i,j}として
0: もわらない
1: もらって、それを選び方に使わない
2: もらって、それを選び方に使う
を、制約を満たすように決めたものに対応します。
制約は
各人から1つ選ぶので $ 1 = \sum_{j=0}^{K-1} \delta_{x_{i,j}, 2}
各日に配るクッキーは与えられているので$ a_j = \sum_{i=0}^{N-1} \delta_{x_{i,j}, 1} + \delta_{x_{i,j}, 2}
このような選び方の場合の数を考えます。
$ {\rm dp}_{i,j}を$ i日終わったときに、決まっている部分で$ x_{i,j} = 2となるものが$ j個なものの場合の数とします。
$ i + 1日目では、$ x_{i+1,j} = 2となるようなものがさらに$ k個増える場合
まだ選べる$ N - j人から$ k人を選ぶ $ {}_{N-j} C_{k}
$ a_i - k個のクッキーを残りの人にわりふる $ {}_{N-k} C_{a_i - k}
ことになるので、$ {\rm dp}_{i+1,j+k} \leftarrow {\rm dp}_{i,j} \times {}_{N-j} C_{k} \times {}_{N-k} C_{a_i - k}
計算量は$ O(KN^2)です。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int main() {
int N, K;
cin >> N >> K;
vector<int> a(K);
Combination<ModInt> comb(N);
vector<vector<ModInt>> dp(K + 1, vector<ModInt>(N + 1, 0));
rep(i, K) rep(j, N + 1) {
for (int k = 0; k <= ai; ++k) { }
}
return 0;
}
ModInt, Combinationに関しては提出コードを見てください。
参考
https://www.youtube.com/watch?v=TIiDKDNFob0&feature=youtu.be