JOI '11 春合宿３：1 - 解読
問題
https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day3.pdf
解法
「dp(i) := i 文字目から L 文字目までで考えられる原文の数の総和」と DP を立てる．このとき，S[i] と同じ文字が出てくる位置を p とすると，
dp(i) = dp(i + 1) + dp(i + 2) + ... + dp(p)
という漸化式が立つ．足し合わせる段階で各規則に反する組み合わせのものは除外する．各規則に反するかどうかを map に入れておくなどすれば O(logM) で確認できる．O(LlogM)．
解答
DP の漸化式を立てるのが甘く，嘘 DP で 1 WA してしまった．
