問題一覧 > 通常問題

No.3080 Colonies on Line

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 6.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 23
作問者 : 👑 binap / テスター : kaichou243 👑 hamamu
お気に入りにしたユーザー ProblemId : 11941 / 自分の提出
問題文最終更新日: 2025-03-24 23:43:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 462 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。