No.3080 Colonies on Line
タグ : / 解いたユーザー数 21
作問者 : 👑
binap
/ テスター :
kaichou243
hamamu
問題文
整数からなる集合 $S$ であって、その全ての要素 $x \in S$ について以下が成り立つとき、 $S$ をよい集合であるといいます。
$y \in S \setminus \{x\}$ かつ $x-K \leq y \leq x + K$ を満たす整数 $y$ が存在する。
集合 $\{1,2, \cdots, N\}$ の部分集合は $2^N$ 個あります。このうちよい集合であるものはいくつあるでしょう。答えはとても大きな値になる場合があるので素数 $998244353$ で割った余りを出力してください。
制約
$1\leq N \leq 10^{12}$
$1\leq K \leq 50000$
$K \leq N$
入力は全て整数。
入力
$N$ $K$
出力
条件を満たす集合の個数を $998244353$ で割った余りを $1$ 行で出力してください。
サンプル
サンプル1
入力
5 1
出力
12
$\{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\}$ の $12$ 通りです。
例えば $S = \{1, 2, 4, 5\}$ はよい集合です。実際
要素 $1 \in S$ について、 $2 \in S\setminus \{1\}$ かつ $1-K\leq 2 \leq 1 +K$ です。
要素 $2 \in S$ について、 $1 \in S\setminus \{2\}$ かつ $2-K\leq 1 \leq 2 +K$ です。
要素 $4 \in S$ について、 $5 \in S\setminus \{4\}$ かつ $4-K\leq 5 \leq 4 +K$ です。
要素 $5 \in S$ について、 $4 \in S\setminus \{5\}$ かつ $5-K\leq 4 \leq 5 +K$ です。
一方 $S=\{1, 4\}$ はよい集合ではありません。実際
要素 $1 \in S$ について、 $y \in S\setminus \{1\}$ かつ $1-K\leq y \leq 1 +K$ を満たす整数 $y$ は存在しません。
サンプル2
入力
6 2
出力
42
サンプル3
入力
314 159
出力
674265274
答えを素数 $998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。