問題一覧 > 通常問題

No.3080 Colonies on Line

レベル : / 実行時間制限 : 1ケース 6.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : 👑 binap / テスター : kaichou243 hamamu
1 ProblemId : 11941 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-24 23:43:06

問題文

整数からなる集合 SS であって、その全ての要素 x∈Sx \in S について以下が成り立つとき、 SS をよい集合であるといいます。

  • y∈S∖{x}y \in S \setminus \{x\} かつ x−K≤y≤x+Kx-K \leq y \leq x + K を満たす整数 yy が存在する。

集合 {1,2,⋯ ,N}\{1,2, \cdots, N\} の部分集合は 2N2^N 個あります。このうちよい集合であるものはいくつあるでしょう。答えはとても大きな値になる場合があるので素数 998244353998244353 で割った余りを出力してください。

制約

  • 1≤N≤10121\leq N \leq 10^{12}

  • 1≤K≤500001\leq K \leq 50000

  • K≤NK \leq N

  • 入力は全て整数。

入力

NN KK

出力

条件を満たす集合の個数を 998244353998244353 で割った余りを 11 行で出力してください。

サンプル

サンプル1
入力
5 1
出力
12

{1,2,3,4,5}\{1,2, 3, 4, 5\} の部分集合のうちよい集合であるものは ∅,{1,2},{2,3},{3,4},{4,5},{1,2,3},{2,3,4},{3,4,5},{1,2,3,4},{1,2,4,5},{2,3,4,5},{1,2,3,4,5}\emptyset, \{1, 2\}, \{2, 3\}, \{3, 4\}, \{4, 5\}, \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 5\}, \{1, 2, 3, 4\}, \{1,2,4,5\}, \{2, 3, 4, 5\}, \{1,2,3,4,5\} の 1212 通りです。

例えば S={1,2,4,5}S = \{1, 2, 4, 5\} はよい集合です。実際

  • 要素 1∈S1 \in S について、 2∈S∖{1}2 \in S\setminus \{1\} かつ 1−K≤2≤1+K1-K\leq 2 \leq 1 +K です。

  • 要素 2∈S2 \in S について、 1∈S∖{2}1 \in S\setminus \{2\} かつ 2−K≤1≤2+K2-K\leq 1 \leq 2 +K です。

  • 要素 4∈S4 \in S について、 5∈S∖{4}5 \in S\setminus \{4\} かつ 4−K≤5≤4+K4-K\leq 5 \leq 4 +K です。

  • 要素 5∈S5 \in S について、 4∈S∖{5}4 \in S\setminus \{5\} かつ 5−K≤4≤5+K5-K\leq 4 \leq 5 +K です。

一方 S={1,4}S=\{1, 4\} はよい集合ではありません。実際

  • 要素 1∈S1 \in S について、 y∈S∖{1}y \in S\setminus \{1\} かつ 1−K≤y≤1+K1-K\leq y \leq 1 +K を満たす整数 yy は存在しません。

サンプル2
入力
6 2
出力
42
サンプル3
入力
314 159
出力
674265274

答えを素数 998244353998244353 で割った余りを出力してください。

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