問題一覧 > 通常問題

No.1832 NAND Reversible

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : rianoriano / テスター : 👑 H20H20 👑 ygussanyygussany
8 ProblemId : 7446 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-10 19:13:05

問題文

$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]]]]]$
です。また、 NAND 演算とは $[0,0]=[0,1]=[1,0]=1, [1,1]=0$ を満たす演算です。

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。