問題一覧 > 通常問題

No.2060 AND Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 86
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : chineristACchineristAC nok0nok0 👑 ygussanyygussany
1 ProblemId : 8320 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-26 20:53:05

問題文

長さ $N$ の非負整数列 $A$ であって、 以下の条件を満たすものの個数を求めてください。（$\mathrm{AND}$はビットごとの論理積を表します。）

  • $0 \le A_i \le M　(1 \le i \le N) $
  • $A_i$ $\mathrm{AND}$ $A_{i+1} =A_i　(1 \le i \le N-1)$
ただし、答えは非常に大きくなる場合があるので、$998244353$ で割った余りを答えてください。

入力

$N$ $M$

  • $2 \le N \le 2×10^5 $
  • $1 \le M < 2^{30} $
  • 与えられる入力は全て整数

    • 出力

    条件を満たす $A$ の個数を $998244353$ で割った余りを出力してください。

    サンプル

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

    例えば $A=(0,1,3)$ などが条件を満たします。

    サンプル2
    入力
    6 29
    出力
    7735

    サンプル3
    入力
    100000 1000000000
    出力
    808693061

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