Codeforces ラウンド #235 (ディビジョン 2) D. ローマ字と数字(状態压dp)_html/css_WEB-ITnose

ローマ字と数字

テストごとの制限時間

4 秒

テストごとのメモリ制限

512 メガバイト

入力

標準入力

出力

標準出力

ローマンは若い数学者で、ウーシュラントでは非常に有名です。残念ながら、セレヤさんはそうは思っていません。セレジャの考えを変えさせるために、ローマンはどんな数学的問題も解決する準備ができています。少し考えた後、セレハはローマに、m を法として数値 n に近い数値がいくつあるかを見つけるように頼みました。

数値 x は、m を法として数値 n に近いと見なされます。次の場合:

数値 n の桁を並べ替えることで取得できる、

先行ゼロはありません、

数値 x を m で割った後の剰余は 0 に等しいです。

ローマンは優れた数学者ですが、そのような数の数は彼にとって大きすぎます。そこで彼はあなたに手伝ってほしいと頼んでいます。

入力

最初の行には、n (1?≤?n?1018) と m (1?≤?m?≤?100) の 2 つの整数が含まれています。 .

出力

単一行に単一の整数を出力します。数値 n 法 m に近い数値の数。

サンプル テスト

入力

104 2

出力

入力

223 4

出力

入力

rree

出力

7067678 8

注記

最初のサンプルで必要な数値は 104、140、410 です。

2 番目のサンプルで必要な数値は 232 です。

意: 1 つの数字と m を出力し、再配列num 内の各位の数字にどのような数 (mod m) = 0 があるか、直接枚全配列肯定不行、可用状態压dp来搞..

dp[S][k] は、num 中の S および (mod m)=k の方式数を示し、初期条件 dp[0][0]=1、移動方は dp[i|1