No.3080 Colonies on Line
タグ : / 解いたユーザー数 23
作問者 : 👑
hamamu
Problem Statement
Let $S$ be a set of integers. If the following holds for all of its elements $x \in S$, then $S$ is called a good set.
There exists an integer $y$ satisfying $y \in S \setminus \{x\}$ and $x-K \leq y \leq x + K$.
The set $\{1,2, \cdots, N\}$ has $2^N$ subsets. How many of them are good sets? Since the answer can be very large, output it modulo the prime $998244353$.
Constraints
$1\leq N \leq 10^{12}$
$1\leq K \leq 50000$
$K \leq N$
All inputs are integers.
Input
$N$ $K$
Output
Output on $1$ line the number of sets satisfying the condition, modulo $998244353$.
Sample
Sample 1
Input
5 1
Output
12
The subsets of $\{1,2, 3, 4, 5\}$ that are good sets are the following: $\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\}$, for a total of $12$.
For example, $S = \{1, 2, 4, 5\}$ is a good set. Indeed:
For the element $1 \in S$, we have $2 \in S\setminus \{1\}$ and $1-K\leq 2 \leq 1 +K$.
For the element $2 \in S$, we have $1 \in S\setminus \{2\}$ and $2-K\leq 1 \leq 2 +K$.
For the element $4 \in S$, we have $5 \in S\setminus \{4\}$ and $4-K\leq 5 \leq 4 +K$.
For the element $5 \in S$, we have $4 \in S\setminus \{5\}$ and $5-K\leq 4 \leq 5 +K$.
On the other hand, $S=\{1, 4\}$ is not a good set. Indeed:
For the element $1 \in S$, there is no integer $y$ satisfying $y \in S\setminus \{1\}$ and $1-K\leq y \leq 1 +K$.
Sample 2
Input
6 2
Output
42
Sample 3
Input
314 159
Output
674265274
Output the answer modulo the prime $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。