https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c
長さ$N$の整数列が与えられる。「整数のうち1つを選んで2で割る（小数点以下切捨て）」という操作を$K$回行って得られる可能性がある数列の数を$10^9+7$で割ったあまりを求めよ。
まず、$i$番目の数について何回2で割ると0になるかを表した数列を作る。これらの和は最大でも3000程度なので、$K\geq 4000$であれば$4000$くらいにしておいていい（答えが変わらないため）。
DPテーブルを $$DP[i][j][flag]=i{\rm 番目の数までで}j{\rm 回操作をしたときに作れる数列の数}$$ とする。ただし、$flag=0$は操作後の数列に1つも0が含まれていないことを、$flag=1$は操作後の数列に0が含まれていることを表す。ここで、0に対してはそれ以上操作しないものとする（実際には可能であるが）。
数列に0が含まれていない場合は$K$回ちょうどの操作で作れる数列の数を見なくてはいけないが、数列に0が1つでもあればその0に対して操作をし続けることでいくらでも本質的な操作回数を減らすことができる。よって、求める答えは $$DP[N][K][0]+\sum_{k=0}^K DP[N][k][1]$$ となる。
まさかDPとは。