AT_abc300_h [ABC300Ex] Fibonacci: Revisited

[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 $ である。

N/A

N/A

### 制約 - $ 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 $ になります。