Integer Transmission (UVa Live Archive Asia - Site 3 (China) - 2007/2008 Beijing (China))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4031

問題

最大dの遅延が生じるネットワーク上で長さnのビット列の送信を行う。送信するビット列を与えるので送信される可能性のあるビット列の個数とその最小値、最大値を答えよ。
1<=n<=64
0<=d<=n

解法

ビット列の個数はメモ化再帰で求める。calc(zero, one)はzero番目の0まで使用し、one番目の1まで使用した状態で残りのビット列は何通りあるか返す関数である。0,1は貪欲に使用して問題ない。現在のindexは0のインデックスと1のインデックスの小さい方を取る。
ビット列の最小値・最大値は0を優先して使用するか、1を優先して使用すれば作れる。
たぶんlong longだとオーバーフローするのでunsigned long longを使うこと。