dowangoプログラミングコンテスト決勝 A.ニコニコ文字列2

問題

0〜9,?によって構成されるN文字の文字列が与えられる。
ニコニコ文字列を2525...5のように「25」が連続した文字列とすると、上記の文字列からニコニコ文字列を取り出す方法がX通り以上だったことがわかっている。
このとき、元の文字列として考えられるものは何通りあるか、mod 10^9+7で求めよ。

1<=N<=252
0<=X<=252

考え方

i-1文字まで処理が終わってるとして、i文字目を考えたとき、「i文字目までで2525...が何文字続いているか？」がわかると、この2525...から取り出せるニコニコ文字列の取り出し方が求められる。(k文字続いているとして、偶数文字目ならば1+2+...+k/2がi文字目までの取り出し方)

そこで、必要な状態をdpテーブルにして、
dp[i][j][k][l]:=i文字がjだったとき、2525...がk個続いていて、ニコニコ文字列の組み合わせ数の累計がl通りであるような、文字列の組み合わせ数
を考えると求められる。
しかし、252*10^2*252*l=635040*l回計算が必要。lは、かなり大きくなりうる。
(10^2は...??...のような場合、?がそれぞれ10通りずつあるので、組み合わせで10^2)

lがX通り以上だったらXにつぶす、ような方法では、遷移が無い場合もあり得るので、Xにつぶしてしまうと区別できない。
しかし、「X通り以上＝全部-X通り未満」と考えると、全部は10^{?の個数}通りなので、X通り未満の場合の文字列の組み合わせ数を求めればよい。
しかし、それでも1.6*10^9で2秒制限ではきつい。

jとして考えるべきは、0,1,2,3,4,5,6,7,8,9のうち、2,5,その他だけなので、252*3^2*252*252=1.44*10^8になって、ギリギリだけど間に合う。
遷移として、str[i]=?の場合、かつ、その他の場合は、0,1,3,4,6,7,8,9の8通りが考えられるので、前の状態から8倍してあげればよい。

ここまででも解けてしまったが、さらに考えると、ほとんど似たような遷移が多く、jを状態に持たなくてもよいことがわかる。すると、計算量はO(N^2 X)まで落ちる(っぽい)。

https://speakerdeck.com/dwango/dwangopuroguramingukontesuto-ben-xuan-wen-ti-jie-shuo