103007: [Atcoder]ABC300 Ex - Fibonacci: Revisited
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
Problem Statement
We define the general term $a_n$ of a sequence $a_0, a_1, a_2, \dots$ by:
$a_n = \begin{cases} 1 & (0 \leq n \lt K) \\ \displaystyle{\sum_{i=1}^K} a_{n-i} & (K \leq n). \\ \end{cases}$Given an integer $N$, find the sum, modulo $998244353$, of $a_m$ over all non-negative integers $m$ such that $m\text{ AND }N = m$. ($\text{AND}$ denotes the bitwise AND.)
What is bitwise AND?
The bitwise AND of non-negative integers $A$ and $B$, $A\text{ AND }B$, is defined as follows.・When $A\text{ AND }B$ is written in binary, its $2^k$s place ($k \geq 0$) is $1$ if $2^k$s places of $A$ and $B$ are both $1$, and $0$ otherwise.
Constraints
- $1 \leq K \leq 5 \times 10^4$
- $0 \leq N \leq 10^{18}$
- $N$ and $K$ are integers.
Input
The input is given from Standard Input in the following format:
$K$ $N$
Output
Print the answer.
Sample Input 1
2 6
Sample Output 1
21
$a_0$ and succeeding terms are $1, 1, 2, 3, 5, 8, 13, 21, \dots$. Four non-negative integers, $0, 2, 4$, and $6$, satisfy $6 \text{ AND } m = m$, so the answer is $1 + 2 + 5 + 13 = 21$.
Sample Input 2
2 8
Sample Output 2
35
Sample Input 3
1 123456789
Sample Output 3
65536
Sample Input 4
300 20230429
Sample Output 4
125461938
Sample Input 5
42923 999999999558876113
Sample Output 5
300300300
Input
题意翻译
给定正整数 $k$，定义线性递推数列： $$a_n = \begin{cases} 1 \ , \ (0 \leq n < k) \\ \displaystyle\sum_{i=1}^k a_{n-i} \ , \ (n \geq k)\end{cases}$$ 再给定 $n$，对所有「二进制下与 $n$ 的按位与运算后为自身」的自然数 $m$，求 $a_m$ 之和。 比如 $k=2$，$n=6$ 时满足条件的 $m$ 有 $2,4,6$，可以计算出 $a_2+a_4+a_6=21$。Output
分数：600分
部分
问题描述
我们定义序列$a_0, a_1, a_2, \dots$的通项为：
$a_n = \begin{cases} 1 & (0 \leq n \lt K) \\ \displaystyle{\sum_{i=1}^K} a_{n-i} & (K \leq n). \\ \end{cases}$
部分
约束条件
部分 输入 输入从标准输入按以下格式给出： $K$ $N$ 部分 输出 打印答案。
部分 样例输入1
部分 样例输入2
部分 样例输入3
部分 样例输入4
部分 样例输入5
什么是按位与？
非负整数$A$和$B$的按位与$A\text{ AND }B$定义如下。 ・当$A\text{ AND }B$写成二进制时，它的$2^k$s位（$k \geq 0$）为$1$，如果$A$和$B$的$2^k$s位都是$1$，否则为$0$。- $1 \leq K \leq 5 \times 10^4$
- $0 \leq N \leq 10^{18}$
- $N$和$K$为整数。
部分 输入 输入从标准输入按以下格式给出： $K$ $N$ 部分 输出 打印答案。
部分 样例输入1
2 6部分 样例输出1
21
$a_0$和后续项为$1, 1, 2, 3, 5, 8, 13, 21, \dots$。 四个非负整数，$0, 2, 4$和$6$，满足$6 \text{ AND } m = m$，所以答案为$1 + 2 + 5 + 13 = 21$。
部分 样例输入2
2 8部分 样例输出2
35
部分 样例输入3
1 123456789部分 样例输出3
65536
部分 样例输入4
300 20230429部分 样例输出4
125461938
部分 样例输入5
42923 999999999558876113部分 样例输出5
300300300