問題一覧 > 通常問題

No.2511 Mountain Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : GlinTFraulein / テスター : PCTprobability 👑 Mizar 👑 amentorimaru 👑 獅子座じゃない人
2 ProblemId : 9868 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-10-20 22:21:56

問題文

正整数 N,MN,M が与えられます。ここで、以下の条件を満たすような長さ NN の正整数列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N) を「山型数列」と呼ぶことにします。

  • ある 11 以上 NN 以下の整数 ii が存在して、以下を全て満たす。
    • A1<A2<…<AiA_1 < A_2 < … < A_i
    • Ai>Ai+1>…>ANA_i > A_{i+1} > … > A_N
    • Ai≤MA_i \le M

「山型数列」の個数を 998244353998244353 で割ったあまりを求めてください。

制約

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤M≤2×1051 \le M \le 2 \times 10^5
  • 入力は全て整数

入力

N MN\ M

出力

「山型数列」の個数を 998244353998244353 で割ったあまりを出力せよ。

サンプル

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

「山型数列」は (1,2,3,1)(1, 2, 3, 1)、(1,2,3,2)(1, 2, 3, 2)、(1,3,2,1)(1, 3, 2, 1)、(2,3,2,1)(2, 3, 2, 1) の 44 個です。

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

条件を満たす「山型数列」が存在しない場合もあります。

サンプル3
入力
12345 123456
出力
412894584

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