No.2017 Mod7 Parade
タグ : / 解いたユーザー数 87
作問者 :
souta-1326
/ テスター :
penguinman
Problem Statement
You are given a sequence $D$ of length $K$ consisting of $1$-digit non-negative integers, and a sequence $L$ of length $K$ consisting of positive integers.
Here, let $S$ be a non-empty subsequence of $(1,2,\ldots K)$. (The original order is preserved.)
Let $k$ be the length of $S$, and define $f(S)$ as the integer formed by arranging, starting from the most significant digit, $L_{S_1}$ copies of $D_{S_1}$, $L_{S_2}$ copies of $D_{S_2}$, $\ldots$ , $L_{S_k}$ copies of $D_{S_k}$. Here, $f(S)$ may have a leading $0$.
There are $2^K-1$ ways to choose $S$. For all of them, compute "the remainder of $f(S)$ divided by $7$", and find the sum of these values modulo $(10^9+7)$.
Input
$K$ $D_1$ $L_1$ $D_2$ $L_2$ $\vdots$ $D_K$ $L_K$
・All inputs are integers.
・$1 \leq K \leq 10^5$
・$0 \leq D_i \leq 9$
・$1 \leq L_i \leq 10^9$
・$D_1 \neq 0$
Output
For every possible $S$, compute the remainder of $f(S)$ divided by $7$, and output the sum of these values modulo $(10^9+7)$.
Sample
Sample 1
Input
3 5 4 2 7 1 5
Output
16
When $S=(1)$, $f(S)=5555$, and its remainder when divided by $7$ is $4$.
When $S=(2)$, $f(S)=2222222$, and its remainder when divided by $7$ is $2$.
When $S=(3)$, $f(S)=11111$, and its remainder when divided by $7$ is $2$.
When $S=(1,2)$, $f(S)=55552222222$, and its remainder when divided by $7$ is $0$.
When $S=(1,3)$, $f(S)=555511111$, and its remainder when divided by $7$ is $1$.
When $S=(2,3)$, $f(S)=222222211111$, and its remainder when divided by $7$ is $5$.
When $S=(1,2,3)$, $f(S)=5555222222211111$, and its remainder when divided by $7$ is $2$.
Summing these gives $4+2+2+0+1+5+2=16$, so output $16$.
Sample 2
Input
10 5 325056811 9 679667253 5 142418837 3 231318149 3 795021347 0 14971591 8 259744487 3 210609568 5 219691049 8 957754853
Output
3048
Cases where $f(S)$ has a leading $0$, such as $S=(6,7)$, are also counted.
Sample 3
Input
3 1 5 1 5 1 5
Output
27
Even if the values of $f(S)$ are the same, count them separately if they are formed from different $S$.
Also, since the answer can be very large, find the remainder when divided by $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。