問題一覧 > 通常問題

No.1832 NAND Reversible

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 58
作問者 : riano / テスター : ygussany H20
お気に入りにしたユーザー ProblemId : 7446 / 自分の提出
問題文最終更新日: 2022-01-10 19:13: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 330 (順位表) の他の問題:

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]]]]]$
Here, the NAND operation is the operation satisfying $[0,0]=[0,1]=[1,0]=1, [1,1]=0$.

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