No.372 It's automatic
タグ : / 解いたユーザー数 85
作問者 :
koba-e964
/ テスター :
🍡yurahuna
Note
注意: 想定解はC++で実装されており、最悪ケースで1秒～2秒程度かかります(制限時間は6秒)。他の言語で実装した場合時間切れになる可能性が高いです。Javaでは3667msです。
テスター解のPython(PyPy)ではTLEになります。
問題文
'0'から'9'までの文字からなる文字$S$と、正の整数$M$が与えられます。
1文字以上の部分列であって10進数として解釈したものが$M$の倍数となるようなものの総数をmod 1,000,000,007$=10^9 + 7$で出力してください。
ここで、文字列$S$の部分列とは、
$1 \le a_1 < a_2 < \cdots < a_k\le |S|$
なる$(a_i)_i$を用いて$S[a_1]S[a_2]\cdots S[a_k]$と表せる文字列のことです。($S[i]$は$S$の$i$番目の文字)
位置が異なり文字列としては同じ部分列は異なるものとして扱います。例えば$S="110"$の場合、
1文字目と3文字目からなる部分列"10"と
2文字目と3文字目からなる部分列"10"は別々に数えます。
また、部分列が2文字以上の場合は0から始まるものは数えません。例えば$S="02", M = 2$の場合、"02"は2の倍数とはみなしません。
入力
$S$ $M$
$1 \le |S| \le 10,000$
$1 \le M \le 20,000$
$S$の各文字は'0'から'9'である。
サンプルケースのうちファイル名が"testcase-small1-"で始まるものは、$1 \le |S| \le 16, 1 \le M \le 1,000 $を満たす。
サンプルケースのうちファイル名が"testcase-small2-"で始まるものは、$1 \le |S| \le 10,000, 1 \le M \le 1,000 $を満たす。
出力
結果を出力してください。 最後に改行してください。
サンプル
サンプル1
入力
012 3
出力
2
0,12の2種類存在します。012は0から始まり2文字以上なので数えません。
サンプル2
入力
220 2
出力
7
2(1文字目), 2(2文字目), 0, 22, 20(1文字目と3文字目), 20(2文字目と3文字目), 220の7種類存在します。
サンプル3
入力
123456789123456789 1
出力
262143
$262143 = 2^{18} - 1$です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。