No.2703 FizzBuzz Letter Counting
タグ : / 解いたユーザー数 20
作問者 :
hamamu
Magentor
Problem Statement
Find the number of characters when doing FizzBuzz with the integers from $1$ to $N$, inclusive, modulo $998244353$.
More precisely, with $f(x)$ defined as follows, find $\sum_{i=1}^{N} f(i)\mod 998244353$.
$f(x)=\begin{cases}8(x\bmod 15= 0)\\4(x\bmod 3=0\land x\bmod 5\ne 0)\\4(x\bmod 5=0\land x\bmod 3\ne 0)\\ \lfloor \log_{ 10 } x\rfloor+1 (\text{otherwise.})\end{cases}$
However, $N$ is not given directly in the input. Instead, you are given a sequence $((v_1,l_1),(v_2,l_2),\dots,(v_M,l_M))$ of length $M$, which is the run-length encoding of $N$. It is guaranteed that $v_1\ne 0$, but it is not necessarily the case that $v_i\ne v_{i+1}$.
$N$ can be obtained as follows.
- Concatenate $l_1$ copies of $v_1$, $l_2$ copies of $v_2$, …, $l_M$ copies of $v_M$, in this order, and interpret the result as a base-$10$ number.
Input
$M$ $v_1\ l_1$ $v_2\ l_2$ $\vdots$ $v_M\ l_M$
- $1\leq M\leq 10^5$
- $0\leq v_i\leq 9$
- $v_1\ne 0$
- $1\leq l_i\leq 10^{12}$
- All input values are integers.
Output
Output the answer on $1$ line.
Sample
Sample 1
Input
2 1 1 5 1
Output
43
$N=15$. Doing FizzBuzz with the integers from $1$ to $15$, inclusive, gives 1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz, and the number of characters excluding the delimiters is $43$.
Sample 2
Input
3 1 1 0 8 7 1
Output
884608017
$N=1000000007$. The exact answer is $6874074135$, but you should output $884608017$, its remainder modulo $998244353$.
Sample 3
Input
10 1 1000000000000 2 1000000000000 3 1000000000000 4 1000000000000 5 1000000000000 6 1000000000000 7 1000000000000 8 1000000000000 9 1000000000000 0 1000000000000
Output
354927044
$N$ can be a very large integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。