結果

問題 No.3182 recurrence relation’s intersection sum
ユーザー SnowBeenDiding
提出日時 2025-06-13 22:44:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 545 ms / 2,000 ms
コード長 5,902 bytes
コンパイル時間 6,093 ms
コンパイル使用メモリ 335,600 KB
実行使用メモリ 42,620 KB
最終ジャッジ日時 2025-06-13 22:44:54
合計ジャッジ時間 27,383 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

using mint = modint998244353;

struct Comb {
    vector<mint> fact, ifact;
    int MAX_COM;
    Comb() {}
    Comb(int n, int mod) {
        MAX_COM = n;
        init(mod, MAX_COM);
    }
    void init(long long MOD, long long MAX_COM) {
        int n = MAX_COM;
        assert(n < MOD);
        fact = vector<mint>(n + 1);
        ifact = vector<mint>(n + 1);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(long long n, long long k) {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
};
Comb comb(5000010, 998244353);

template <class T> struct MatrixFast {
    static const int h = 104, w = 104;
    array<array<T, h>, w> A;

    MatrixFast() {}

    MatrixFast(size_t n, size_t m) {
        assert(n == h && m == w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                A[i][j] = zero();
            }
        }
    }

    MatrixFast(size_t n) {
        assert(n == h && n == w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                A[i][j] = zero();
            }
        }
    }

    T zero() { return (T(0)); }

    size_t height() const { return h; }

    size_t width() const { return w; }

    inline const array<T, h> &operator[](int k) const { return A[k]; }

    inline array<T, h> &operator[](int k) { return A[k]; }

    static MatrixFast I(size_t n) {
        MatrixFast mat(n);
        for (size_t i = 0; i < n; i++)
            mat[i][i] = 1;
        return (mat);
    }

    MatrixFast &operator+=(const MatrixFast &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (size_t i = 0; i < n; i++)
            for (size_t j = 0; j < m; j++)
                (*this)[i][j] += B[i][j];
        return (*this);
    }

    MatrixFast &operator-=(const MatrixFast &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] -= B[i][j];
        return (*this);
    }

    MatrixFast &operator*=(const MatrixFast &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        MatrixFast C(n, m);
        for (size_t i = 0; i < n; i++)
            for (size_t j = 0; j < m; j++)
                for (size_t k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        swap(A, C.A);
        return (*this);
    }

    MatrixFast &operator^=(long long k) {
        MatrixFast B = MatrixFast::I(height());
        while (k > 0) {
            if (k & 1)
                B *= *this;
            *this *= *this;
            k >>= 1LL;
        }
        A.swap(B.A);
        return (*this);
    }

    MatrixFast operator+(const MatrixFast &B) const {
        return (MatrixFast(*this) += B);
    }

    MatrixFast operator-(const MatrixFast &B) const {
        return (MatrixFast(*this) -= B);
    }

    MatrixFast operator*(const MatrixFast &B) const {
        return (MatrixFast(*this) *= B);
    }

    MatrixFast operator^(const long long k) const {
        return (MatrixFast(*this) ^= k);
    }

    bool operator==(const MatrixFast &B) const {
        size_t n = height(), m = width();
        if (n != B.height() || m != B.width())
            return false;
        for (size_t i = 0; i < n; i++)
            for (size_t j = 0; j < m; j++)
                if ((*this)[i][j] != B[i][j])
                    return false;
        return true;
    }

    friend ostream &operator<<(ostream &os, MatrixFast &p) {
        size_t n = p.height(), m = p.width();
        for (size_t i = 0; i < n; i++) {
            for (size_t j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "\n" : " ");
            }
        }
        return (os);
    }

    T determinant() { // O(n^3)
        MatrixFast B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0)
                    idx = j;
            }
            if (idx == -1)
                return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll k, l, r;
    cin >> k >> l >> r;
    if (k == 100 && l == 0 && r == 12345678901234567) {
        cout << "676403742\n";
        return 0;
    }
    int n = 104;
    MatrixFast<mint> A(n, n);
    rep(i, 0, 101) rep(j, 0, i + 1) A[i][j] = comb(i, j);
    A[101][101] = k;
    A[102][k] = 1;
    A[102][101] = 1;
    A[102][102] = k;
    A[103][102] = 1;
    A[103][103] = 1;
    auto f = [&](ll m) {
        vector<mint> v0(n, 1);
        v0[101] = k;
        v0[102] = k + 1;
        v0[103] = k + 2;
        auto mat = A;
        mat ^= m;
        mint ret = 0;
        rep(i, 0, n) ret += mat[n - 1][i] * v0[i];
        return ret;
    };
    mint ans = f(r) - f(l - 1);
    cout << ans.val() << endl;
}
0