問題一覧 > 通常問題

No.2839 AND Constraint

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 38
作問者 : milkcoffeemilkcoffee / テスター : とりゐとりゐ ygussanyygussany
1 ProblemId : 11236 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-08-03 20:24:11

問題文

あなたは変数 $x=0$ を持っています。各 $i = 1,2,\dots,2^N-1$ について順番に以下の操作を行います。

  • $k$ を「$i$ を 二進表記したときに末尾に連続する $0$ の個数」とする。 $($例えば、 $i=6$ のとき、 $6$ の二進表記は $110$ であるため $k=1$ である。$)$
    $0 \leq y \leq 2^k$ かつ、 $(x+y) \ \text{AND} \ i = (x+y)$ を満たす整数 $y$ を選び、$x$ を $x+y$ で置き換える。

ただし、$\text{AND}$ は bit ごとの論理積を表します。操作の具体的な例はサンプル $1$ をご覧ください。

$2^N-1$ 回の操作のうち、 $M$ 回は $y \geq 1$ として操作を行い、残りの $2^N-1-M$ 回は $y=0$ として操作を行います。

$2^N-1$ 回の操作列としてあり得るものの数を $998244353$ で割ったあまりを求めて下さい。

ただし、$2$ つの操作列が同じであるとは、「どの操作についても、選んだ整数 $y$ が等しいこと」とします。

入力

$N$ $M$

  • $1 \leq N,M \leq 500$
  • 入力は全て整数

出力

答えを整数で出力してください。

サンプル

サンプル1
入力
2 2
出力
2

行う操作は $2^N-1 = 3$ 回で、そのうち $y \geq 1$ として操作を行った回数が $2$ 回のものを数えます。

あり得る $2$ 通りの操作列について、各操作の前後における $x$ を表すと以下の通りです。$($矢印の上の整数はその操作で選んだ $y$ の値$)$

  • $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$

    • 例えば、以下のような操作列は存在し得ません。

  • $0 \overset{1}{\to} 1 \overset{0}{\to} 1 \overset{2}{\to} 3$ $\dots (2$ 回目の操作で $(x+y) \ \text{AND} \ i = (x+y)$ を満たさない。$)$
  • $0 \overset{0}{\to} 0 \overset{0}{\to} 0 \overset{3}{\to} 3$ $\dots (3$ 回目の操作で $y \leq 2^k$ を満たさない。$)$
    • サンプル2
    入力
    3 7
    出力
    1

    以下の $1$ 通りのみが条件を満たします。$($表記は サンプル $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$
    • サンプル3
    入力
    1 500
    出力
    0

    操作を $1$ 回しか行わないため、$y \geq 1$ として操作を行えるのは高々 $1$ 回です。よって明らかに条件を満たす操作列は存在しません。

    サンプル4
    入力
    234 432
    出力
    611707541

    答えを $998244353$ で割ったあまりを求めてください。

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