結果

問題 No.3182 recurrence relation’s intersection sum
ユーザー lif4635
提出日時 2025-06-13 22:33:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 342 ms / 2,000 ms
コード長 2,733 bytes
コンパイル時間 3,501 ms
コンパイル使用メモリ 286,540 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-13 22:33:54
合計ジャッジ時間 10,049 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Pythonの元コードをC++に忠実に翻訳したもの
// オリジナルのアルゴリズムや定数、変数名は保持

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 998244353;
const ll inf = 1001001001001001001LL;

struct Comb {
    vector<ll> fac, finv;
    int mod;
    Comb(int lim, int mod_ = 998244353): fac(lim+1), finv(lim+1), mod(mod_) {
        fac[0] = fac[1] = 1;
        for (int i = 2; i <= lim; ++i) fac[i] = fac[i-1] * i % mod;
        finv[lim] = powmod(fac[lim], mod - 2);
        for (int i = lim; i >= 2; --i) finv[i-1] = finv[i] * i % mod;
        finv[0] = 1;
    }

    ll powmod(ll a, ll b) const {
        ll res = 1;
        a %= mod;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    ll C(int a, int b) const {
        if (b < 0 || a < b) return 0;
        return fac[a] * finv[b] % mod * finv[a - b] % mod;
    }
};

using Matrix = vector<vector<ll>>;

Matrix mat_mul(const Matrix &a, const Matrix &b) {
    int n = a.size(), m = b[0].size(), l = b.size();
    Matrix res(n, vector<ll>(m));
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < l; ++k)
            for (int j = 0; j < m; ++j)
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
    return res;
}

Matrix mat_pow2(const Matrix &a) {
    int n = a.size();
    Matrix res(n, vector<ll>(n));
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k)
            for (int j = 0; j < n; ++j)
                res[i][j] = (res[i][j] + a[i][k] * a[k][j]) % mod;
    return res;
}

Matrix mat_pow(Matrix a, ll exp) {
    int n = a.size();
    Matrix res(n, vector<ll>(n));
    for (int i = 0; i < n; ++i) res[i][i] = 1;
    for (int i = 63; i >= 0; --i) {
        if ((exp >> i) & 1) res = mat_mul(res, a);
        if (i == 0) return res;
        res = mat_pow2(res);
    }
    return res;
}

ll solve(int k, ll x, const Comb& comb) {
    int d = k + 4;
    Matrix mat(d, vector<ll>(d));

    mat[0][0] = k;
    mat[0][d - 2] = 1;
    mat[0][d - 1] = 1;

    mat[1][0] = 1;
    mat[1][1] = 1;

    for (int m = 0; m <= k; ++m)
        for (int j = 0; j <= m; ++j)
            mat[2 + m][2 + j] = comb.C(m, j);

    mat[d - 1][d - 1] = k;

    Matrix res = mat_pow(mat, x);

    Matrix v(d, vector<ll>(1));
    v[0][0] = 1;
    v[2][0] = 1;
    v[d - 1][0] = 1;

    Matrix final = mat_mul(res, v);
    return final[1][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    ll l, r;
    cin >> k >> l >> r;

    Comb comb(1000);

    ll ans = (solve(k, r + 1, comb) - solve(k, l, comb) + mod) % mod;
    cout << ans << '\n';
}
0