No.1677 mæx
タグ : / 解いたユーザー数 105
作問者 :
stoq
/ テスター :
akakimidori
sak
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,2are 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,eto? - $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もしくは右上の雲マークをクリックしてアカウントを作成してください。