結果

問題 No.2883 K-powered Sum of Fibonacci
ユーザー Iroha_3856Iroha_3856
提出日時 2024-08-13 18:17:50
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 17 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 67 ms
6,948 KB
testcase_08 AC 14 ms
6,944 KB
testcase_09 AC 6 ms
6,940 KB
testcase_10 AC 7 ms
6,944 KB
testcase_11 AC 149 ms
6,940 KB
testcase_12 AC 14 ms
6,944 KB
testcase_13 AC 7 ms
6,940 KB
testcase_14 AC 176 ms
6,944 KB
testcase_15 AC 45 ms
6,940 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 21 ms
6,940 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 23 ms
6,940 KB
testcase_20 AC 223 ms
6,944 KB
testcase_21 AC 211 ms
6,944 KB
testcase_22 AC 228 ms
6,944 KB
testcase_23 AC 170 ms
6,940 KB
testcase_24 AC 174 ms
6,944 KB
testcase_25 AC 242 ms
6,940 KB
testcase_26 AC 256 ms
6,940 KB
testcase_27 AC 265 ms
6,944 KB
testcase_28 AC 253 ms
6,944 KB
testcase_29 AC 218 ms
6,940 KB
testcase_30 AC 5 ms
6,940 KB
testcase_31 AC 1 ms
6,944 KB
testcase_32 AC 2 ms
6,940 KB
testcase_33 AC 8 ms
6,940 KB
testcase_34 AC 1 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 1 ms
6,940 KB
testcase_37 AC 1 ms
6,940 KB
testcase_38 AC 2 ms
6,940 KB
testcase_39 AC 1 ms
6,940 KB
testcase_40 AC 1 ms
6,940 KB
testcase_41 AC 1 ms
6,944 KB
testcase_42 AC 224 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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