[ABC300Ex] Fibonacci: Revisited
题意翻译
给定正整数 $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$ 有 $0, 2,4,6$，可以计算出 $a_0 + a_2+a_4+a_6=21$。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc300/tasks/abc300_h
数列 $ 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} $ はビット単位 AND)
ビット単位 AND とは？ 整数 $ A,B $ のビット単位 AND、$ A\text{\ AND\ }B $ は以下のように定義されます。
・$ A\text{\ AND\ }B $ を二進表記した際の $ 2^k $ $ (k\ \geq\ 0) $ の位の数は、$ A,B $ を二進表記した際の $ 2^k $ の位の数のうち両方が $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ K $ $ N $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
2 6输出样例 #1
21输入样例 #2
2 8输出样例 #2
35输入样例 #3
1 123456789输出样例 #3
65536输入样例 #4
300 20230429输出样例 #4
125461938输入样例 #5
42923 999999999558876113输出样例 #5
300300300说明
### 制約
- $ 1\ \leq\ K\ \leq\ 5\ \times\ 10^4 $
- $ 0\ \leq\ N\ \leq\ 10^{18} $
- $ N,\ K $ は整数
### Sample Explanation 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 $ になります。