問題一覧 > 通常問題

No.2019 Digits Filling for All Substrings

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 76
作問者 : Shirotsume / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 7678 / 自分の提出
問題文最終更新日: 2022-04-25 13:20:00
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 353 （オムニバス） (順位表) の他の問題:

Problem Statement

For a string $X$ consisting of the digits 0-9 and ?, let $f(X)$ be the answer to the following problem.

    Problem: Consider a string $X'$ obtained by replacing each ? in $X$ with $1$ character among the digits 0-9. If $X$ contains $k$ occurrences of ?, there are $10^k$ possible strings $X'$. How many of them are multiples of $3$ when regarded as integers after removing unnecessary leading $0$ characters?

For a string $S$, we denote by $S[L:R]$ the substring of $S$ consisting of the $L$-th through $R$-th characters.

You are given a string $S$ of length $N$ consisting of the digits 0-9 and ?. Find $\displaystyle \sum_{L = 1}^{N} \sum_{R = L}^{N} f(S[L:R])$ modulo $998244353$.

Constraints

  • All input values are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $S$ is a string of length $N$ consisting of the digits 0-9 and ?.

Input

The input is given from Standard Input in the following format. 
$N$
$S$

Output

Print the answer, followed by a newline.

Sample

Sample 1
Input
3
1?3
Output
15

The value of $f$ is shown below for each non-empty substring of $S$.

  • For $S[1:1] =$ 1, we have $f(S[1:1]) = 0$.
  • For $S[2:2] =$ ?, the multiples of $3$ that can be made by replacing ? with 0-9 are the following $4$: $0, 3, 6, 9$. Thus, $f(S[2:2]) = 4$.
  • For $S[3:3] =$ 3, we have $f(S[3:3]) = 1$.
  • For $S[1:2] =$ 1?, the multiples of $3$ that can be made are $12, 15, 18$, which is $3$ values, so $f(S[1:2]) = 3$.
  • For $S[2:3] =$ ?3, the multiples of $3$ that can be made are $3, 33, 63, 93$, which is $4$ values, so $f(S[2:3]) = 4$. The first character may be $0$.
  • For $S[1:3] =$ 1?3, the multiples of $3$ that can be made are $123, 153, 183$, which is $3$ values, so $f(S[1:3]) = 3$.

Therefore, the answer is $0 + 4 + 1 + 3 + 4 + 3 = 15$.

Sample 2
Input
5
12345
Output
7

$S$ may contain no ?.

Sample 3
Input
3
???
Output
414

$S$ may consist only of ?.

Sample 4
Input
32
31415926????????23846264????????
Output
945855420

Find the answer modulo $998244353$.

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