問題一覧 > 通常問題

No.2017 Mod7 Parade

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : souta-1326souta-1326 / テスター : penguinmanpenguinman
2 ProblemId : 6717 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-10 10:08:21

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。