問題一覧 > 通常問題

No.2839 AND Constraint

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

問題文

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

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

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

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

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

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

入力

NN MM

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

出力

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

サンプル

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

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

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

  • 0→00→22→130 \overset{0}{\to} 0 \overset{2}{\to} 2 \overset{1}{\to} 3
  • 0→11→12→020 \overset{1}{\to} 1 \overset{1}{\to} 2 \overset{0}{\to} 2

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

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

    以下の 11 通りのみが条件を満たします。((表記は サンプル 11 と同様))

  • 0→11→12→13→14→15→16→170 \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

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

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

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

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