問題一覧 > 通常問題

No.3349 AtCoder Janken Train

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : りすりす/TwoSquirrels / テスター : ponjuice jupiter_68 noya2
ProblemId : 12822 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-11-13 17:29:33
コンテストの他の問題:

問題文

区別可能な $2^N$ 人が AtCoder じゃんけん列車を行います。$2^N$ 人のうち $M$ 人は「寒色」、残りの $2^N - M$ 人は「暖色」です。

AtCoder じゃんけん列車を終えた後、最終的にできる列の並び方としてあり得るものの総数を $998244353$ で割ったあまりを求めてください。

ただし、AtCoder じゃんけん列車とは、以下の操作として定義されます。

  • まず、$2^N$ 人がそれぞれ $1$ 人からなる列を $2^N$ 個作ります。
  • $N \ge 1$ のとき、$t = 0, 1, \dots, N - 1$ の整数 $t$ についてこの順に、以下の操作を行います。
    1. 現在の列の数を $K = 2^{N-t}$ とします。
    2. これら $K$ 個の列を、任意の方法で $\dfrac{K}{2}$ 個のペアに分割します。
    3. 分割してできた $\dfrac{K}{2}$ 個の各ペア $(L_A, L_B)$ に対して、それぞれ以下の操作を行い、$\dfrac{K}{2}$ 個の新しい列を作ります。
      • $L_A$ の先頭の人を $h_A$、 $L_B$ の先頭の人を $h_B$ とします。
      • $h_A$ と $h_B$ で、どちらか一方が勝つまでじゃんけんをします。
      • $h_A$ が「寒色」、 $h_B$ が「暖色」の場合、$L_A$ を $L_B$ の後ろに結合して新しい列を作ります。
      • $h_A$ が「暖色」、 $h_B$ が「寒色」の場合、$L_B$ を $L_A$ の後ろに結合して新しい列を作ります。
      • どちらでもない場合、じゃんけんで $h_A$ が勝った場合は $L_B$ を $L_A$ の後ろに、$h_B$ が勝った場合は $L_A$ を $L_B$ の後ろに結合して新しい列を作ります。

すべての操作を終えた後、列はただ $1$ つになっています。

制約

  • $0 \le N \le 18$
  • $0 \le M \le 2^N$
  • $N, M$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

出力

答えを出力せよ。

サンプル

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

寒色 $2$ 人を $A, B$、暖色 $2$ 人を $C, D$ とします。

このとき、具体的な操作の一例は次のようになります。

  • $t=0$ のとき
    • $K = 2^{2-0} = 4$
    • 作られたペア: $((A), (C))$ と $((B), (D))$
    • じゃんけんの勝敗: $A$ が $C$ に勝ち、$D$ が $B$ に勝った
    • 得られる列: $(C, A)$ と $(D, B)$
  • $t=1$ のとき
    • $K = 2^{2-1} = 2$
    • 作られたペア: $((C, A), (D, B))$
    • じゃんけんの勝敗: $C$ が $D$ に勝った
    • 得られる列: $(C, A, D, B)$

あり得る最終的な列は $(C, A, D, B)$、$(C, B, D, A)$、$(C, D, A, B)$、$(C, D, B, A)$、$(D, A, C, B)$、$(D, B, C, A)$、$(D, C, A, B)$、$(D, C, B, A)$ の $8$ 通りとなるため、8 を出力してください。

サンプル2
入力
3 0
出力
40320

$2^3 = 8$ 人全員が暖色であるため、どの列の先頭も常に暖色同士となり、結合順は常に $2$ 択です。よって総数は $8! = 40320$ となります。

サンプル3
入力
18 192109
出力
659921266

$998244353$ で割ったあまりを出力することに注意してください。

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