ACPC2012Day2OL A.ID

問題

n桁のIDのチェックを行う。チェックは各桁について、右端を1桁目として、偶数桁の数字を2倍してすべての桁を足したものが10で割り切れるかどうかで確認する。2倍して2桁になった場合はそれらをさらに分割し、それを足したものを用いる。
IDには*が含まれ、そこに入りうる数字のリストが与えられる。
チェックが通るIDの組み合わせがいくつありえるかを答える。

1<=n<=100000
1<=*の数<=7

考え方

まず*の数が少ないので、全探索すればよい。ただし、nが大きいため、毎回計算してしまうと時間がかかりすぎてしまう。
桁がずれることがないので、IDで数字が連続している部分について、あらかじめ計算しておき圧縮する。(あらかじめ計算しておいて、走査するときスキップ先を保存して計算した)