これは手間取ったけど解けて良かった。
http://community.topcoder.com/stat?c=problem_statement&pm=15008
問題
N人の人が円形に並んでいる。
i番の人は自身の銃を(i+1)%N番に向けている。
N人の人が順に銃を撃つことを考える。
銃を向けた先の人が生きていればその人は死亡する。
ただし撃つ順番の人が先に死んでいた場合、その人が銃を撃てない。
銃の撃ち方はN!通りあるが、そのうち最終的にA人生き残る順番は何通りか。
解法
初手、1番の人が撃ったとする。
すると2番の人は死亡し、3番の人は死ぬことはない。
下記DPを考える。解はN*(N-1)*dp(N-2,A)となる。最初のNは誰が最初に撃つか、2番目の(N-1)は、(実質何も起きないが)2番目の人が撃つ順番は残り(N-1)人のうちどこに来るかを示している。
dp(N,A) := N人の人が並んでいて、その後に順番完了済みの人が1人いる場合、A人残っている撃ち方の組み合わせ
dp(N,A)は次にN人中誰が撃つかを考えていけばよく、全体でO(N^3)で済む。
ll mo=1000000007; ll memo[160][160]; const int CN=401; ll C[CN][CN]; class Gangsters { public: ll dfs(int P,int A) { if(A<1) return 0; if(A>P+1) return 0; if(P<=1) return A==1; if(memo[P][A]>=0) return memo[P][A]; ll ret=0; for(int i=1;i<=P;i++) { if(i==1) { ret+=(P-1)*dfs(P-2,A-1)%mo; } else if(i==P) { ret+=dfs(P-1,A); } else { int x,y; ll tmp=0; for(x=0;x<=A;x++) { y=A-x; tmp+=dfs(i-1,x)*dfs(P-(i+1),y)%mo; } ret+=(P-1)*(tmp%mo)%mo*C[P-2][i-1]%mo; } } return memo[P][A]=ret%mo; } int countOrderings(int people, int alive) { MINUS(memo); int i,j; FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo; return people*(people-1)*dfs(people-2,alive)%mo; } }
まとめ
方針はすぐ立ったけど、実装を詰めるのにだいぶ手間取った。