No.2017 Mod7 Parade
タグ : / 解いたユーザー数 87
作問者 :
souta-1326
/ テスター :
penguinman
問題文
$1$ 桁の非負整数から成る長さ $K$ の数列 $D$ と、正整数から成る長さ $K$ の数列 $L$ が与えられます。
ここで、$(1,2,\ldots K)$ の空でない部分列を $S$ とおきます。（元の順番は保持します。）
$S$ の長さを $k$ として、$f(S)$ を 上の桁から順に $D_{S_1}$ が $L_{S_1}$ 個、$D_{S_2}$ が $L_{S_2}$ 個、$\ldots$ 、 $D_{S_k}$ が$L_{S_k}$ 個並んだ整数と定義します。ここで、$f(S)$ の先頭が $0$ であっても構いません。
$S$ の作り方は $2^K-1$ 通りありますが、それら全てについて「$f(S)$ を $7$ で割った余り」を求め、その総和を $(10^9+7)$ で割った余りを求めてください。
入力
$K$ $D_1$ $L_1$ $D_2$ $L_2$ $\vdots$ $D_K$ $L_K$
・入力は全て整数である。
・$1 \leq K \leq 10^5$
・$0 \leq D_i \leq 9$
・$1 \leq L_i \leq 10^9$
・$D_1 \neq 0$
出力
考えられる全ての $S$ に対して $f(S)$ を $7$ で割った余りを求め、それらの総和を $(10^9+7)$ で割った余りを出力してください。
サンプル
サンプル1
入力
3 5 4 2 7 1 5
出力
16
$S=(1)$ の時、$f(S)=5555$ となり、これを $7$ で割った余りは $4$ です。
$S=(2)$ の時、$f(S)=2222222$ となり、これを $7$ で割った余りは $2$ です。
$S=(3)$ の時、$f(S)=11111$ となり、これを $7$ で割った余りは $2$ です。
$S=(1,2)$ の時、$f(S)=55552222222$ となり、これを $7$ で割った余りは $0$ です。
$S=(1,3)$ の時、$f(S)=555511111$ となり、これを $7$ で割った余りは $1$ です。
$S=(2,3)$ の時、$f(S)=222222211111$ となり、これを $7$ で割った余りは $5$ です。
$S=(1,2,3)$ の時、$f(S)=5555222222211111$ となり、これを $7$ で割った余りは $2$ です。
これらを合計すると $4+2+2+0+1+5+2=16$ となるので、$16$ を出力します。
サンプル2
入力
10 5 325056811 9 679667253 5 142418837 3 231318149 3 795021347 0 14971591 8 259744487 3 210609568 5 219691049 8 957754853
出力
3048
$f(S)$ の先頭が $0$ のとき、例えば $S=(6,7)$ のときもカウントします。
サンプル3
入力
3 1 5 1 5 1 5
出力
27
$f(S)$ の値が同じでも、異なる $S$ によって作られている場合は別々にカウントしてください。
また、答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。