SRM 477 Div2 Hard CarelessSecretary
問題
カードがN枚あり、各カードはそれぞれの袋に入っている。このカードをシャッフルして袋に入れなおし、この内K枚を取り出したときにK枚全てがもともとの袋にはいっていたものではなかった。このようなシャッフルの数はいくらか?
やりかた
いくつかの解き方があるようだが、ここは包除原理で解く。
K枚が一つも合っていない状態数は、
(全状態数)-(K枚あっている)∨(K-1枚あっている)∨(K-2枚あっている)∨・・・∨(1枚あっている)
ということができる。これは包除原理に書き直せば
(全状態数)-((少なくとも1枚あっている)-(少なくとも2枚あっている)+(少なくとも3枚あっている)・・・(-1)^(K+1)(少なくともK枚あっている))
となる。第一項の(全状態数)というのは(少なくとも0枚あっている)と置き換えられるのでまとめて書いてしまえば答えは
(:K枚中少なくともi枚あっているようなシャッフル数)
となる。
以下ソース。
ll fact[1001]; class CarelessSecretary { public: int howMany(int N, int K) { ll result = 0; fact[0] = 1; for(int i = 1; i <= 1000; i++) fact[i] = ((ll)fact[i - 1] * i) % MOD; for(int i = 0; i < 1 << K; i++){ int c = __builtin_popcount(i); if(c % 2) result = (result - fact[N - c] + MOD) % MOD; else result = (result + fact[N - c] + MOD) % MOD; } return (int)result % MOD; } };
Get up! 明日のSUPER ST@R!