http://community.topcoder.com/stat?c=problem_statement&pm=15008
円状にpeople人いる。
i番目の人がもし生きていれば、(i+1)番目の人を銃で撃つ（N-1番目は0番目を撃つ）。
どの順番で銃を撃つかはN!通りあるが、この中で生存者がalive人となるのは何通り？
前提知識
解法
まずは、公式解説にもある性質に気がつく必要がある。
No matter which gangster starts shooting, the situation will be perfectly symmetric.
誰が最初に撃ったかにかかわらず、全ての状況は同じになる。
つまり、最初が0で後ろが1～people-1の順列のうち生存者がalive人である組合せと最初が1で後ろが0,2～people-1の順列のうち生存者がalive人である組合せと…はすべて等しい。
なので、（最初が0で後ろが1～people-1の順列のうち生存者がalive人である組合せ）を求めて×peopleすれば答えになる。
これは挿入DPで答えよう。
dp[i][shoot][L][isAlive] := i番目まで確定していて、撃った回数がshoot回で、最後の人がL番目に入っていて、最後の人の生死isAliveのときの組合せ
最初は先頭に置いて、当然撃てるので、初期状態はdp[1][1][0][1] = 1;
dp[i][shoot][L][isAlive]からの遷移を考えよう。
挿入後に[0,L]の位置にある場合は、i番目の人より前で撃っているので、i番目の生死にかかわらずi+1番目は生存する。
挿入後に[L+1,i+1)の位置にある場合は、i番目の人より後ろで撃っているので、
- i番目が生きていればi+1番目は打たれて死んでしまう
- i番目が死んでいればi+1番目は生きる
という感じで遷移させる。
最後に答えを集計するが、「撃った回数＝死亡者の数」なので、生存者ではなく死亡者がpeople-aliveでの組合せを考えて集計しよう。
O(N^4)だが、単純なDPは結構速い。
mint dp[151][151][151][2]; // dp[i][shoot][L][isAlive] // i番目まで確定していて、撃った回数がshoot回で、最後の人がL番目に入っていて、最後の人の生死isAlive struct Gangsters { int countOrderings(int people, int alive) { int N = people; rep(i, 0, 151) rep(shoot, 0, 151) rep(L, 0, 151) rep(isAlive, 0, 2) dp[i][shoot][L][isAlive] = 0; // 最初の人が撃った dp[1][1][0][1] = 1; rep(i, 1, N) rep(shoot, 0, N) rep(L, 0, N) { // 最後の人より前で撃てば、必ず生存しているので撃てる rep(LL, 1, L + 1) dp[i + 1][shoot + 1][LL][1] += dp[i][shoot][L][0] + dp[i][shoot][L][1]; // 最後の人より後で打つ場合は。。。 rep(RR, L + 1, i + 1) { dp[i + 1][shoot][RR][0] += dp[i][shoot][L][1]; // 最後の人が生きてれば、死ぬ dp[i + 1][shoot + 1][RR][1] += dp[i][shoot][L][0]; // 最後の人が死んでれば、生きる } } mint ans = 0; int dead = people - alive; rep(L, 0, N) ans += dp[N][dead][L][0] + dp[N][dead][L][1]; return (ans * people).get(); } };
