AT_abc300_h [ABC300Ex] Fibonacci: Revisited

题目描述

数列 $a_0,\ a_1,\ a_2,\ \dots$ 的通项 $a_n$ 定义如下：

$$a_n = \begin{cases} 1 & (0 \leq n < K) \\ \displaystyle{\sum_{i=1}^K} a_{n-i} & (K \leq n) \\ \end{cases}$$

给定整数 $N$。请计算所有满足 $m\ \text{AND}\ N = m$ 的非负整数 $m$ 的 $a_m$ 之和，并对 $998244353$ 取模后输出。($\text{AND}$ 表示按位与运算)

按位与运算的定义如下：对于整数 $A,B$，$A\ \text{AND}\ B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数值为 $A,B$ 的二进制表示中第 $2^k$ 位都为 $1$ 时为 $1$，否则为 $0$。

输入格式

输入从标准输入读取，格式如下：

$K$ $N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 6

输出 #1

21

输入输出样例 #2

输入 #2

2 8

输出 #2

35

输入输出样例 #3

输入 #3

1 123456789

输出 #3

65536

输入输出样例 #4

输入 #4

300 20230429

输出 #4

125461938

输入输出样例 #5

输入 #5

42923 999999999558876113

输出 #5

300300300

说明/提示

限制条件

• $1 \leq K \leq 5 \times 10^4$
• $0 \leq N \leq 10^{18}$
• $N, K$ 均为整数

样例解释 1

数列各项从 $a_0$ 开始依次为 $1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ \dots$。满足 $6\ \text{AND}\ m = m$ 的非负整数有 $0,\ 2,\ 4,\ 6$ 共 $4$ 个，因此答案为 $1 + 2 + 5 + 13 = 21$。

由 ChatGPT 4.1 翻译