問題一覧 > 通常問題

No.2839 AND Constraint

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 41
作問者 : milkcoffee / テスター : とりゐ ygussany
お気に入りにしたユーザー ProblemId : 11236 / 自分の提出
問題文最終更新日: 2024-08-03 20:24:11
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 440 (順位表) の他の問題:

Problem Statement

You have a variable $x=0$. For each $i = 1,2,\dots,2^N-1$ in order, perform the following operation.

  • Let $k$ be "the number of consecutive $0$s at the end of the binary representation of $i$". $($For example, when $i=6$, the binary representation of $6$ is $110$, so $k=1$.$)$
    Choose an integer $y$ satisfying $0 \leq y \leq 2^k$ and $(x+y) \ \text{AND} \ i = (x+y)$, and replace $x$ with $x+y$.

Here, $\text{AND}$ denotes the bitwise logical AND. See Sample $1$ for concrete examples of the operations.

Among the $2^N-1$ operations, $M$ operations are performed with $y \geq 1$, and the remaining $2^N-1-M$ operations are performed with $y=0$.

Find the number of possible sequences of $2^N-1$ operations, modulo $998244353$.

Here, $2$ sequences of operations are considered the same if "the chosen integer $y$ is equal for every operation".

Input

$N$ $M$

  • $1 \leq N,M \leq 500$
  • All input values are integers

Output

Output the answer as an integer.

Sample

Sample 1
Input
2 2
Output
2

$2^N-1 = 3$ operations are performed, and we count the sequences in which the number of operations performed with $y \geq 1$ is $2$.

For the $2$ possible sequences of operations, the value of $x$ before and after each operation is shown below. $($The integer above each arrow is the value of $y$ chosen in that operation.$)$

  • $0 \overset{0}{\to} 0 \overset{2}{\to} 2 \overset{1}{\to} 3$
  • $0 \overset{1}{\to} 1 \overset{1}{\to} 2 \overset{0}{\to} 2$

    • For example, the following sequences of operations are impossible.

  • $0 \overset{1}{\to} 1 \overset{0}{\to} 1 \overset{2}{\to} 3$ $\dots (2$nd operation does not satisfy $(x+y) \ \text{AND} \ i = (x+y)$.$)$
  • $0 \overset{0}{\to} 0 \overset{0}{\to} 0 \overset{3}{\to} 3$ $\dots (3$rd operation does not satisfy $y \leq 2^k$.$)$
    • Sample 2
    Input
    3 7
    Output
    1

    Only the following $1$ sequence satisfies the conditions. $($The notation is the same as in Sample $1$.$)$

  • $0 \overset{1}{\to} 1 \overset{1}{\to} 2 \overset{1}{\to} 3 \overset{1}{\to} 4 \overset{1}{\to} 5 \overset{1}{\to} 6 \overset{1}{\to} 7$
    • Sample 3
    Input
    1 500
    Output
    0

    Since the operation is performed only $1$ time, an operation with $y \geq 1$ can be performed at most $1$ time. Therefore, clearly no sequence of operations satisfies the conditions.

    Sample 4
    Input
    234 432
    Output
    611707541

    Find the answer modulo $998244353$.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。