One of the Best Hackers in the World!

Facebook HackerCupのsemifinalが迫ります。

finalには行けなくてもT-shirtが欲しいです。

ロゴはこんな感じ。

"You are one of the best hackers in the world.

certified by Facebook"

やばい。。

今日は1Aの問題を解いてみた。「Wine Tasting」という問題。

g本ワインを試飲して、c本以上正しく正解する場合のパターン数を求めよ。という問題。

Ai = {1,2,3,4, ... g}と定義すれば、Ai == iとなる要素数がc以上になる場合の数列のパターン数を求めよ。

という問題に帰着できる。

SjをAi==iとなる要素数がj個である場合のパターン数と定義すると、求める値が

Sum_{c <= j <= g} Sj

となるのは自明。

あとは、Sjの求め方を考えればよい。

まず、Ai==iとなる場所を選ぶパターンは、gCjである。

次に、残ったg-j個をAi == iとならないように並べる。

このパターン数をptn(j)とおくと、

ptn(j) = (j-1) * (ptn(j-1) + ptn(j-2))という漸化式が成り立つ。

これは、難しいので解説。（これに気付くのに2日かかった。。。この問題解いた人は閃いたのか？それとも知っていたのか？？）

j-1個のAi==iとならないパターン{A1, A2, ..., Aj-1}の後ろにAjをおく。

Ajと任意のAk, 1<=k<=j-1を交換してもこの数列は、Ai == i, 1<=i<=jとならない。

よって、(j-1) * ptn(j-1)のパターンを数え上げた。

次に、Ajとスワップする要素に関しては、最初の段階でAi==iとなっていても問題ない（スワップするため）。Ai==iとする場所をj-1個の要素から選び、残りのj-2個を並び変えるパターンは、

(j-1) * ptn(j-2)

よって、前述を2つを足して、

ptn(j) = (j-1) * (ptn(j-1) + ptn(j-2))

となるわけである。

むずっ。。

ここまで出来れば、実装は簡単。

コンビネーションは「パスカルの三角形」で計算すればOK。

残ったものの並び変えも、DPで計算すればOK。

あとは、MODULOの比較的大きいため、64bitに入れないと掛け算でオーバーフローするので注意。

ソースはこちら。（今回は何回もチャレンジして書きなおしたため、最終的なソースは結構きれい。。）

#define MOD 1051962371
uint64_t cmb[126][126];
uint64_t ptn[126];

int main() {
   cmb[0][0] = 1;
   FOR (i, 1, 126) cmb[i][0] = 1;
   FOR (i, 1, 126)FOR (j, 1, i+1)
       cmb[i][j] = (cmb[i-1][j-1] + cmb[i-1][j]) % MOD;

   ptn[0] = 1, ptn[1] = 0;
   FOR (i, 2, 126) {
       ptn[i] = (i-1) * (ptn[i-1] + ptn[i-2]);
       ptn[i] %= MOD;
   }

   int n, g, c;
   cin >> n;
   while (n--) {
       cin >> g >> c;
       uint64_t ret = 0;
       FOR(i, c, g+1) {
           int t = cmb[g][i] * ptn[g-i] % MOD;
           ret = (ret + t) % MOD;
       }
       cout << ret << endl;
   }

   return 0;
}