問題一覧 > 通常問題

No.2703 FizzBuzz Letter Counting

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : hirayuu_yc / テスター : hamamu Magentor
0 ProblemId : 10242 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-15 10:57:04

問題文

11 以上 NN 以下の整数でFizzBuzzをしたときの文字数を 998244353998244353 で割った余りを求めてください。

より厳密には、f(x)f(x) を以下のように定義したときの ∑i=1Nf(i)mod  998244353\sum_{i=1}^{N} f(i)\mod 998244353 を求めてください。

f(x)={8(x mod 15=0)4(x mod 3=0∧x mod 5≠0)4(x mod 5=0∧x mod 3≠0)⌊log⁡10x⌋+1(otherwise.)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}

ただし、NN は入力で直接与えられず、その代わりに NN を連長圧縮した長さ MM の列 ((v1,l1),(v2,l2),…,(vM,lM))((v_1,l_1),(v_2,l_2),\dots,(v_M,l_M)) が与えられます。v1≠0v_1\ne 0 は保証されますが、vi≠vi+1v_i\ne v_{i+1} とは限りません。

NN は、以下のようにして得ることができます。

  • v1v_1 を l1l_1 個、v2v_2 を l2l_2 個、…、vMv_M を lMl_M 個、この順につなげたものを 1010 進数の数として解釈する。

入力

MM
v1 l1v_1\ l_1
v2 l2v_2\ l_2
⋮\vdots
vM lMv_M\ l_M
  • 1≤M≤1051\leq M\leq 10^5
  • 0≤vi≤90\leq v_i\leq 9
  • v1≠0v_1\ne 0
  • 1≤li≤10121\leq l_i\leq 10^{12}
  • 入力はすべて整数

出力

11 行で、答えを出力してください。

サンプル

サンプル1
入力
2
1 1
5 1
出力
43

N=15N=15 です。11 以上 1515 以下の整数でFizzBuzzをすると 1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz となり、区切り文字を除いた文字数は 4343 文字です。

サンプル2
入力
3
1 1
0 8
7 1
出力
884608017

N=1000000007N=1000000007 です。正しい答えは 68740741356874074135 ですが、998244353998244353 で割った余りである 884608017884608017 を出力してください。

サンプル3
入力
10
1 1000000000000
2 1000000000000
3 1000000000000
4 1000000000000
5 1000000000000
6 1000000000000
7 1000000000000
8 1000000000000
9 1000000000000
0 1000000000000
出力
354927044

NN が非常に大きな整数になることもあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。