別解として Fiduccia’s algorithm を利用した解法を説明します。(俗に「高速きたまさ法」と呼ばれているアルゴリズムです)

Fiduccia’s algorithm では, \(a_n = \sum_{i=1}^K c_i a_{n-i}\ (n \geq K)\) を満たす数列の第 \(N\) 項は次の手順で求まります。(詳しい説明は省略します)

• \(C(x) = c_K + c_{K-1} x + \dots + c_{1} x^{K-1} -x^K\) とする。
• \(x^N\) を \(C(x)\) で割った余りを求める。これを \(R(x) = r_0 + r_1 x + \dots + r_{K-1} x^{K-1}\) とする。
• \(r_0 a_0 + r_1 a_1 + \dots + r_{K-1} a_{K-1}\) が求める答えである。

この問題は、\(m \text{ AND }N = m\) を満たす \(m\) に対する \(a_m\) の総和を求める問題です。よって

\[C(x) = 1 + x + \dots + x^{K-1} - x^K\]

\[ F(x) = \sum_{m \text{ AND } N = m} x^m\]

とすると \(F(x) \bmod C(x)\) が計算できればよいとわかります。これは

\[F(x) = \prod_{2^b \text{ AND } N = 2^b} \left(1 + x^{2^b} \right)\]

と変形できるのを利用すると、\(x^{2^b} \bmod C(x)\) をダブリングの要領で全て計算して適宜かけ合わせることで計算できます。また、\(\text{mod }C(x)\) を取る操作は累積和を利用すれば \(\mathrm{O}(K)\) で計算できるので、畳み込みがあれば以上の演算を全体で \(\mathrm{O}(K \log K \log N)\) で計算できます。

• 実装例(C++)

#include <iostream>
#include <vector>
using namespace std;

#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

int main() {
  long long K, N;
  cin >> K >> N;
  // mod 1+x+...+x^{K-1}-x^K
  auto rem = [&K](vector<mint> f) -> vector<mint> {
    vector<mint> rui(f.size() + 1);
    for (int i = f.size() - 1; i >= 0; i--) {
      f[i] += (rui[i] += rui[i + 1]);
      if (i >= K) {
        rui[i - 1] += f[i];
        if (i != K) rui[i - (K + 1)] -= f[i];
        f[i] = 0;
      }
    }
    return {begin(f), begin(f) + min<int>(f.size(), K)};
  };
  vector<mint> f{1}, base{0, 1};
  for (int i = 0; i < 60; i++) {
    if ((N >> i) & 1) {
      base[0] += 1;
      f = rem(atcoder::convolution(f, base));
      base[0] -= 1;
    }
    base = rem(atcoder::convolution(base, base));
  }
  cout << accumulate(begin(f), end(f), mint{}).val() << "\n";
}