No.1832 NAND Reversible
タグ : / 解いたユーザー数 56
作問者 :
riano
/ テスター :
👑 
ygussany
H20
問題文
$N$ 項からなり、各項の値が $0$ または $1$ である数列 $A_1$,$A_2$,...,$A_N$ に対して、前から順に NAND 演算を行った結果を $X$ 、
後ろから順に NAND 演算を行った結果を $Y$ とします。
すなわち、$[s,t]$ で $s$ と $t$ の NAND の値を表すものとすると、
- $X$ = $[[[[[A_1,A_2],A_3],A_4]...],A_N]$
- $Y$ = $[A_1,[A_2,[...[A_{N-2},[A_{N-1},A_N]]]]]$
$K$ 個の $0$ と $N-K$ 個の $1$ からなる数列で、 $X=Y$ であるものはいくつあるでしょうか。 答えを $998244353$ で割った余りを求めてください。ただし、$2$ つの数列に対して、ある項の値が違う場合のみこれらを異なるものとして数えます。
入力
$N$ $K$
- $2\leq N \leq 2\times 10^5$
- $0 \leq K \leq N$
- 入力は全て整数である
出力
答えを $998244353$ で割った余りを出力してください。 最後に改行してください。
サンプル
サンプル1
入力
3 1
出力
1
$3$ 項からなり、$0$ が $1$ 個（したがって $1$ が $2$ 個）である数列は $(0,1,1),(1,0,1),(1,1,0)$ の $3$ つあります。
このうち、$(0,1,1)$ について見ると、
$X$ $=$ $[[0,1],1]$ $=$ $[1,1]$ $=$ $0$
$Y$ $=$ $[0,[1,1]]$ $=$ $[0,0]$ $=$ $1$
であり条件を満たしていません。$(1,1,0)$ も $X$ と $Y$ が入れ替わるだけなので同様です。
$(1,0,1)$ については、左右対称であることから明らかに $X=Y$ です。よって条件を満たすものは $1$ 通りです。
サンプル2
入力
6 3
出力
10
例えば $(0,0,1,0,1,1)$ は $X=Y=1$ であり条件を満たします。 また、$(1,0,1,0,0,1)$ は $X=Y=0$ であり条件を満たします。 このようなものは全部で $10$ 通りあります。
サンプル3
入力
200000 100101
出力
959639634
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。