No.2703 FizzBuzz Letter Counting
タグ : / 解いたユーザー数 17
作問者 :
hirayuu_yc
/ テスター :
hamamu
Magentor
問題文
$1$ 以上 $N$ 以下の整数でFizzBuzzをしたときの文字数を $998244353$ で割った余りを求めてください。
より厳密には、$f(x)$ を以下のように定義したときの $\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}$
ただし、$N$ は入力で直接与えられず、その代わりに $N$ を連長圧縮した長さ $M$ の列 $((v_1,l_1),(v_2,l_2),\dots,(v_M,l_M))$ が与えられます。$v_1\ne 0$ は保証されますが、$v_i\ne v_{i+1}$ とは限りません。
$N$ は、以下のようにして得ることができます。
- $v_1$ を $l_1$ 個、$v_2$ を $l_2$ 個、…、$v_M$ を $l_M$ 個、この順につなげたものを $10$ 進数の数として解釈する。
入力
$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}$
- 入力はすべて整数
出力
$1$ 行で、答えを出力してください。
サンプル
サンプル1
入力
2 1 1 5 1
出力
43
$N=15$ です。$1$ 以上 $15$ 以下の整数でFizzBuzzをすると 1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz となり、区切り文字を除いた文字数は $43$ 文字です。
サンプル2
入力
3 1 1 0 8 7 1
出力
884608017
$N=1000000007$ です。正しい答えは $6874074135$ ですが、$998244353$ で割った余りである $884608017$ を出力してください。
サンプル3
入力
10 1 1000000000000 2 1000000000000 3 1000000000000 4 1000000000000 5 1000000000000 6 1000000000000 7 1000000000000 8 1000000000000 9 1000000000000 0 1000000000000
出力
354927044
$N$ が非常に大きな整数になることもあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。