結果

問題 No.2883 K-powered Sum of Fibonacci
ユーザー Iroha_3856Iroha_3856
提出日時 2024-07-29 20:48:46
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 301 ms / 3,000 ms
コード長 1,753 bytes
コンパイル時間 3,287 ms
コンパイル使用メモリ 255,392 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-29 20:50:39
合計ジャッジ時間 8,055 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 20 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 80 ms
6,944 KB
testcase_08 AC 16 ms
6,940 KB
testcase_09 AC 7 ms
6,944 KB
testcase_10 AC 9 ms
6,940 KB
testcase_11 AC 169 ms
6,944 KB
testcase_12 AC 16 ms
6,940 KB
testcase_13 AC 8 ms
6,940 KB
testcase_14 AC 202 ms
6,944 KB
testcase_15 AC 49 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 24 ms
6,944 KB
testcase_18 AC 5 ms
6,940 KB
testcase_19 AC 28 ms
6,940 KB
testcase_20 AC 263 ms
6,944 KB
testcase_21 AC 239 ms
6,940 KB
testcase_22 AC 271 ms
6,940 KB
testcase_23 AC 201 ms
6,944 KB
testcase_24 AC 206 ms
6,944 KB
testcase_25 AC 284 ms
6,940 KB
testcase_26 AC 301 ms
6,940 KB
testcase_27 AC 290 ms
6,940 KB
testcase_28 AC 296 ms
6,940 KB
testcase_29 AC 258 ms
6,940 KB
testcase_30 AC 7 ms
6,944 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 3 ms
6,940 KB
testcase_33 AC 9 ms
6,940 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 2 ms
6,940 KB
testcase_37 AC 2 ms
6,940 KB
testcase_38 AC 4 ms
6,940 KB
testcase_39 AC 2 ms
6,944 KB
testcase_40 AC 2 ms
6,944 KB
testcase_41 AC 2 ms
6,944 KB
testcase_42 AC 258 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();}

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;
}

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);

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);
        }
    }
    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