結果

問題 No.2883 K-powered Sum of Fibonacci
ユーザー Iroha_3856
提出日時 2024-08-13 18:17:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 265 ms / 3,000 ms
コード長 2,064 bytes
コンパイル時間 3,130 ms
コンパイル使用メモリ 255,936 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-13 18:17:58
合計ジャッジ時間 7,208 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;

#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); i++)
#define ll long long

//行列累乗ライブラリ
using mat = vector<vector<mint>>;

int hei(const mat& a) {return (int)a.size();}
int wid(const mat& a) {return (int)a[0].size();}

//行列乗算 O(K^3)
mat mul(const mat& a, const mat& b) {
    int ah = hei(a), aw = wid(a), bh = hei(b), bw = wid(b);
    assert(aw == bh);
    mat c(ah, vector<mint>(bw, 0));
    rep(i, 0, ah) rep(j, 0, bw) {
        rep(k, 0, aw) {
            c[i][j] += a[i][k] * b[k][j];
        }
    }
    return c;
}

//行列累乗 O(K^3 log N)
mat pow(mat a, ll p) {
    assert(hei(a) == wid(a));
    int n = hei(a);
    mat ret(n, vector<mint>(n));
    rep(i, 0, n) ret[i][i] = 1;
    while(p > 0) {
        if (p&1) {
            ret = mul(a, ret);
        }
        a = mul(a, a);
        p>>=1;
    }
    return ret;
}

//二項係数ライブラリ
struct combination {
    vector<mint> fac, infac;
    combination(int n) {
        fac.resize(n+1); infac.resize(n+1);
        fac[0] = 1;
        for (int i = 1; i <= n; i++) fac[i] = fac[i-1]*i;
        infac[n] = fac[n].inv();
        for (int i = n; i >= 1; i--) infac[i-1] = infac[i]*i; 
    }
    mint operator()(int n, int k) {
        if (k > n || k < 0) return 0;
        return fac[n]*infac[k]*infac[n-k];
    }
}comb(100); //comb(n, k) で nCk

int main() {
    ll N; int K; cin >> N >> K;
    
    //行列累乗用の正方行列
    mat M(K+2, vector<mint>(K+2, 0));
    rep(i, 0, K+1) {
        int n = K-i;
        rep(j, 0, K+1) {
            int k = K-j-i;
            M[i][j] = comb(n, k);
        }
    }
    //Sに関する部分
    M[K+1][0] = M[K+1][K+1] = 1;
    //行列累乗後
    mat Mpow = pow(M, N);
    //初期値。F_0 = 0 を利用する
    mat z(K+2, vector<mint>(1, 0));
    z[0][0] = 1;
    //答えとなる行列を求める
    mat ans = mul(Mpow, z);
    //答えを出力
    cout << ans[K+1][0].val() << endl;
}
0