Lights (UVa Live Archive Europe - 2009 Southwestern)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=364&page=show_problem&problem=2507

問題

n個の電球がある。集合Siのon/offを切り替えるという操作をm回行い最初のv個だけがついてる状態にしたい。ただし、Si=Sjとなるようなi,jがあってはいけない。そのような操作の列は何通りあるか？
1<=n,m<=1000

解法

m-1回操作の行い方は(m-1)!(2^n)C(m-1)通りある。m回目の押し方はm-1回目までの操作で決まるが、そのときSm=Siとなると場合がある。これはm回目とi回目の操作を除くとそれ以外の操作でちょうど最初のv個がonになる時に起こる。なのでm-2の時の操作の回数を計算することにより再帰的に答えを計算することが可能。
たぶん解説見たほうが分かりやすい。