AC题解

对于固定的核心数量 k，先把每种宽度的填充方案数看成一个数列，发现它总满足一个固定的线性递推关系。接着用 Bostan‑Mori 算法快速求出任意宽度的前缀和，再用区间长度做平均就得到答案；3 型核心只在偶数宽度上非零，处理时把宽度映射到一半再同理计算。

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

const int MOD = 998244353;
const int G = 3;
const int MAX_K = 505;
const int S_LEN = 6000;               // 足够覆盖 k=501 的递推阶数

int modpow(int a, int64_t e) {
    int res = 1;
    while (e) {
        if (e & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        e >>= 1;
    }
    return res;
}
int modinv(int a) { return modpow(a, MOD - 2); }

int inv_fact[MAX_K + 1];
void precompute() {
    int fact[MAX_K + 1];
    fact[0] = 1;
    for (int i = 1; i <= MAX_K; i++)
        fact[i] = 1LL * fact[i - 1] * i % MOD;
    inv_fact[MAX_K] = modinv(fact[MAX_K]);
    for (int i = MAX_K - 1; i >= 0; i--)
        inv_fact[i] = 1LL * inv_fact[i + 1] * (i + 1) % MOD;
}

void ntt(vector<int> &a, bool invert) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        int wlen = modpow(G, (MOD - 1) / len);
        if (invert) wlen = modpow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; j++) {
                int u = a[i + j];
                int v = 1LL * a[i + j + len / 2] * w % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = 1LL * w * wlen % MOD;
            }
        }
    }
    if (invert) {
        int inv_n = modpow(n, MOD - 2);
        for (int &x : a) x = 1LL * x * inv_n % MOD;
    }
}

vector<int> multiply(const vector<int> &a, const vector<int> &b) {
    if (a.empty() || b.empty()) return {};
    int sz = a.size() + b.size() - 1;
    int n = 1;
    while (n < sz) n <<= 1;
    vector<int> A = a, B = b;
    A.resize(n); B.resize(n);
    ntt(A, false); ntt(B, false);
    for (int i = 0; i < n; i++) A[i] = 1LL * A[i] * B[i] % MOD;
    ntt(A, true);
    A.resize(sz);
    while (!A.empty() && A.back() == 0) A.pop_back();
    return A;
}

// 稳定的 Berlekamp‑Massey
vector<int> berlekamp_massey(const vector<int> &s) {
    int n = s.size();
    vector<int> C(n + 1, 0), B(n + 1, 0);
    C[0] = B[0] = 1;
    int L = 0, m = 1, b = 1;
    for (int i = 0; i < n; i++) {
        int d = s[i];
        for (int j = 1; j <= L; j++)
            d = (d + 1LL * C[j] * s[i - j]) % MOD;
        if (d == 0) {
            ++m;
        } else {
            vector<int> T = C;
            int coef = 1LL * d * modinv(b) % MOD;
            for (int j = m; j <= n; j++)
                C[j] = (C[j] - 1LL * coef * B[j - m] % MOD + MOD) % MOD;
            if (2 * L <= i) {
                L = i + 1 - L;
                B = T;
                b = d;
                m = 1;
            } else {
                ++m;
            }
        }
    }
    C.resize(L + 1);
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

vector<int> base2, base3;
void ensure_base(int type, int len) {
    vector<int> &seq = (type == 2) ? base2 : base3;
    if ((int)seq.size() >= len) return;
    int start = seq.size();
    if (start == 0) {
        if (type == 2) seq = {1, 1};      // f(0)=1, f(1)=1
        else           seq = {1, 3};      // h(0)=1 (n=0), h(1)=3 (n=2)
        start = 2;
    }
    for (int i = start; i < len; i++) {
        if (type == 2) {
            seq.push_back((seq[i - 1] + seq[i - 2]) % MOD);
        } else {
            int val = (4LL * seq[i - 1] - seq[i - 2]) % MOD;
            if (val < 0) val += MOD;
            seq.push_back(val);
        }
    }
}

struct PolyInfo {
    vector<int> P, Q;
    bool zero;
};
PolyInfo cache2[MAX_K + 1], cache3[MAX_K + 1];
bool vis2[MAX_K + 1], vis3[MAX_K + 1];

PolyInfo get_poly(int type, int k) {
    if (type == 2 && vis2[k]) return cache2[k];
    if (type == 3 && vis3[k]) return cache3[k];

    ensure_base(type, S_LEN);
    vector<int> &seq = (type == 2) ? base2 : base3;

    vector<int> s(S_LEN, 0);
    bool all_zero = true;
    for (int i = 0; i < S_LEN; i++) {
        int x = seq[i];
        if (x < k) {
            s[i] = 0;
        } else {
            long long num = 1;
            for (int j = 0; j < k; j++) {
                int factor = x - j;      // x >= k 时 factor > 0
                num = num * factor % MOD;
            }
            s[i] = num * inv_fact[k] % MOD;
            if (s[i] != 0) all_zero = false;
        }
    }

    PolyInfo res;
    if (all_zero) {
        res.zero = true;
        res.Q = {1};
        res.P = {};
    } else {
        res.zero = false;
        res.Q = berlekamp_massey(s);
        int L = (int)res.Q.size() - 1;
        res.P.resize(L);
        for (int i = 0; i < L; i++) {
            long long sum = 0;
            for (int j = 0; j <= i && j < (int)res.Q.size(); j++)
                sum += 1LL * res.Q[j] * s[i - j] % MOD;
            res.P[i] = sum % MOD;
        }
        while (!res.P.empty() && res.P.back() == 0) res.P.pop_back();
    }

    if (type == 2) { cache2[k] = res; vis2[k] = true; }
    else           { cache3[k] = res; vis3[k] = true; }
    return res;
}

int bostan_mori(vector<int> P, vector<int> Q, int64_t N) {
    if (N == 0) return P.empty() ? 0 : P[0];
    while (N > 0) {
        vector<int> Q_neg = Q;
        for (int i = 1; i < (int)Q_neg.size(); i += 2)
            Q_neg[i] = (MOD - Q_neg[i]) % MOD;
        vector<int> U = multiply(P, Q_neg);
        vector<int> V = multiply(Q, Q_neg);
        P.clear();
        if (N % 2 == 0) {
            for (int i = 0; i < (int)U.size(); i += 2) P.push_back(U[i]);
        } else {
            for (int i = 1; i < (int)U.size(); i += 2) P.push_back(U[i]);
        }
        Q.clear();
        for (int i = 0; i < (int)V.size(); i += 2) Q.push_back(V[i]);
        while (!P.empty() && P.back() == 0) P.pop_back();
        while (!Q.empty() && Q.back() == 0) Q.pop_back();
        if (Q.empty()) Q.push_back(1);
        N /= 2;
    }
    return P.empty() ? 0 : P[0];
}

int solve_query(int type, int64_t l, int64_t r, int k) {
    PolyInfo poly = get_poly(type, k);
    if (poly.zero) return 0;

    // 前缀和分母 = Q * (1 - x)
    vector<int> Q_sum = poly.Q;
    Q_sum.push_back(0);
    for (int i = (int)poly.Q.size(); i > 0; i--)
        Q_sum[i] = (Q_sum[i] - poly.Q[i - 1] + MOD) % MOD;
    while (!Q_sum.empty() && Q_sum.back() == 0) Q_sum.pop_back();

    int64_t N_high, N_low;
    if (type == 2) {
        N_high = r;
        N_low = l - 1;
    } else {
        int64_t Lp = (l + 1) / 2;      // 第一个偶数 n 对应的索引
        int64_t Rp = r / 2;            // 最后一个偶数 n 对应的索引
        if (Lp > Rp) return 0;
        N_high = Rp;
        N_low = Lp - 1;
    }

    int S_high = bostan_mori(poly.P, Q_sum, N_high);
    int S_low  = (N_low >= 0) ? bostan_mori(poly.P, Q_sum, N_low) : 0;
    int sum_mod = (S_high - S_low + MOD) % MOD;
    int inv_len = modinv((r - l + 1) % MOD);
    return 1LL * sum_mod * inv_len % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();
    int T, m;
    cin >> T >> m;
    while (T--) {
        int64_t l, r;
        int k;
        cin >> l >> r >> k;
        cout << solve_query(m, l, r, k) << '\n';
    }
    return 0;
}