No.986 Present

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 18
作問者 : tubuann1tubuann1 / テスター : beetbeet
1 ProblemId : 3875 / 出題時の順位表
問題文最終更新日: 2020-02-11 19:02:58

問題文

tubuann君は非負整数の世界に住んでいる不思議な生き物です。
あなたはtubuann君の誕生日に $2^M$ 未満の非負整数からなるサイズ $N$ の集合 $S$ を送ることにしました。
tubuann君ははじめ $0$ にいて、$0$ 回以上の任意の回数、以下の行動を行うことができます。

  • 今いる場所を $a$ とする。
  • $s \in S$ を一つ選んで、 $a \oplus s$ に移動する。
$\oplus$ は bitwise exclusive or を表します。
$f(S)$ をtubuann君が $S$ をもらったときに移動できる場所の集合とします。
以下の値を求めてください。

  • tubuann君が移動できる場所の個数を最大化するように $S$ を定めたとき、tubuann君が移動できる場所の個数。
    すなわち、$\max |f(S)|$。この値を $A$ とします。
  • tubuann君が移動できる場所の個数を最大化するような $S$ の個数。
    すなわち、$|\{S\mid |f(S)|=A\}|$。
  • $S$ がtubuann君が移動できる場所の個数を最大化するとき、tubuann君が移動できる場所の集合の個数。
    すなわち、$|\{f(S)\mid |f(S)|=A\}|$。

ただし、これらの値は非常に大きくなることがあるので $998244353$ で割ったあまりを出力してください。

ある二つの集合が異なるとは、片方の集合には含まれて、もう片方の集合には含まれないような要素が存在することをいいます。

入力

$N\ M$

$1 \leq N \leq M \leq 2 \times 10^5$
入力は全て整数である

出力

tubuann君が移動できる場所の個数を最大化するように $S$ を定めたとき、tubuann君が移動できる場所の個数。
tubuann君が移動できる場所の個数を最大化するような $S$ の個数。
$S$ がtubuann君が移動できる場所の個数を最大化するとき、tubuann君が移動できる場所の集合の個数。
この三つそれぞれの値を $998244353$ で割ったあまりをこの順に空白で区切って一行に出力する。

サンプル

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

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

サンプル3
入力
7 100
出力
128 275646563 10439943

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