Ex - Fibonacci-Revisited
当前没有测试数据。
Ex - 斐波那契：重新审视
分数：$600$ 分
问题描述
我们通过以下方式定义数列 $a_0, a_1, a_2, \dots$ 的通项 $a_n$：
$a_n = \begin{cases} 1 & (0 \leq n \lt 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}$ 表示按位与运算。)
什么是按位与？
非负整数 和 的按位与 定义如下。
・当将 用二进制表示时，它的 位 () 在 和 的 位都为 时为 ，否则为 。
约束条件
- $1 \leq K \leq 5 \times 10^4$
- $0 \leq N \leq 10^{18}$
- $N$ 和 $K$ 是整数。
输入
从标准输入中读入数据，格式如下：
输出
输出答案。
2 6
21
$a_0$ 及随后的项依次为 $1, 1, 2, 3, 5, 8, 13, 21, \dots$。 满足 $6 \text{ AND } m = m$ 的非负整数为 $0, 2, 4, 6$，因此答案为 $1 + 2 + 5 + 13 = 21$。
2 8
35
1 123456789
65536
300 20230429
125461938
42923 999999999558876113
300300300