解いた問題のソースコードと解説など。


SRM 477 Div2 Hard CarelessSecretary

問題

カードがN枚あり、各カードはそれぞれの袋に入っている。このカードをシャッフルして袋に入れなおし、この内K枚を取り出したときにK枚全てがもともとの袋にはいっていたものではなかった。このようなシャッフルの数はいくらか?

やりかた

いくつかの解き方があるようだが、ここは包除原理で解く。
K枚が一つも合っていない状態数は、
(全状態数)-(K枚あっている)∨(K-1枚あっている)∨(K-2枚あっている)∨・・・∨(1枚あっている)
ということができる。これは包除原理に書き直せば
(全状態数)-((少なくとも1枚あっている)-(少なくとも2枚あっている)+(少なくとも3枚あっている)・・・(-1)^(K+1)(少なくともK枚あっている))
となる。第一項の(全状態数)というのは(少なくとも0枚あっている)と置き換えられるのでまとめて書いてしまえば答えは
\sum_{i=0}^{K}(-1)^ia_i
a_i: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!