No.1832 NAND Reversible
Problem Statement
For a sequence $A_1$,$A_2$,...,$A_N$ consisting of $N$ terms, where the value of each term is $0$ or $1$, let $X$ be the result of applying the NAND operation in order from the front,
and let $Y$ be the result of applying the NAND operation in order from the back.
That is, letting $[s,t]$ denote the NAND of $s$ and $t$,
- $X$ = $[[[[[A_1,A_2],A_3],A_4]...],A_N]$
- $Y$ = $[A_1,[A_2,[...[A_{N-2},[A_{N-1},A_N]]]]]$
How many sequences consisting of $K$ occurrences of $0$ and $N-K$ occurrences of $1$ satisfy $X=Y$? Find the answer modulo $998244353$. Here, $2$ sequences are counted as different only if the value of some term differs between them.
Input
$N$ $K$
- $2\leq N \leq 2\times 10^5$
- $0 \leq K \leq N$
- All inputs are integers
Output
Print the answer modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
3 1
Output
1
Among sequences with $3$ terms, those containing $0$ exactly $1$ time (and therefore $1$ exactly $2$ times) are $(0,1,1),(1,0,1),(1,1,0)$, which makes $3$ sequences.
Among these, looking at $(0,1,1)$, we have
$X$ $=$ $[[0,1],1]$ $=$ $[1,1]$ $=$ $0$
$Y$ $=$ $[0,[1,1]]$ $=$ $[0,0]$ $=$ $1$
so the condition is not satisfied. The same holds for $(1,1,0)$, since $X$ and $Y$ are merely swapped.
For $(1,0,1)$, it is clear that $X=Y$ because it is symmetric. Therefore, $1$ sequence satisfies the condition.
Sample 2
Input
6 3
Output
10
For example, $(0,0,1,0,1,1)$ has $X=Y=1$ and satisfies the condition. Also, $(1,0,1,0,0,1)$ has $X=Y=0$ and satisfies the condition. There are $10$ such sequences in total.
Sample 3
Input
200000 100101
Output
959639634
Print the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
riano
H20