問題一覧 > 通常問題

No.2703 FizzBuzz Letter Counting

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : hirayuu_yc / テスター : 👑 hamamu Magentor
お気に入りにしたユーザー ProblemId : 10242 / 自分の提出
問題文最終更新日: 2024-03-15 10:57:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 424 (順位表) の他の問題:

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