問題一覧 > 通常問題

No.1677 mæx

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 105
作問者 : stoq / テスター : akakimidori sak
お気に入りにしたユーザー ProblemId : 6497 / 自分の提出
問題文最終更新日: 2021-08-07 20:42:05
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 313 (順位表) の他の問題:

Problem Statement

There is a valid expression $S$ consisting of $0,1,2$ and the functions ${\rm max,mex}$.

Valid expressions and their values are defined as follows.

  • The digits 0,1,2 are valid expressions, and the value of each is that digit (as a number).
  • If $A,B$ are valid expressions, then max($A$,$B$) is a valid expression, and its value is the larger of the values of $A,B$.
  • If $A,B$ are valid expressions, then mex($A$,$B$) is a valid expression, and its value is the smallest non-negative integer that is equal to neither of the values of $A,B$.
  • Nothing other than the above is a valid expression.

For example, mex(max(1,2),max(0,0)) is a valid expression, and its value is ${\rm mex}({\rm max}(1,2),{\rm max}(0,0)) = {\rm mex}(2,0) = 1$.

The mischievous yuki changed zero or more of the characters 0,1,2,a,e contained in $S$ to ?.

Given $S$ after the changes and an integer $K$, find the number of possible original valid expressions whose value is $K$.

Since the answer can be very large, output it modulo $998244353$.

Input

$S$
$K$

  • $1 \leq |S| \leq 2 \times 10^5$
  • $S$ is a string obtained from a valid expression, as defined in the problem statement, by changing zero or more of its characters 0,1,2,a,e to ?
  • $K = 0,1,2$

Output

Output the number of possible original valid expressions whose value is $K$, modulo $998244353$.

Sample

Sample 1
Input
m?x(1,2)
0
Output
1

In this case, the only valid expression satisfying the condition is mex(1,2).

Sample 2
Input
max(?,mex(0,?))
2
Output
5

Sample 3
Input
m?x(m?x(m?x(?,?),m?x(?,?)),m?x(m?x(?,?),m?x(?,?)))
1
Output
250269

Sample 4
Input
0
1
Output
0

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