結果

問題 No.2883 K-powered Sum of Fibonacci
ユーザー Iroha_3856Iroha_3856
提出日時 2024-08-16 22:22:43
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 212 ms / 3,000 ms
コード長 1,845 bytes
コンパイル時間 4,737 ms
コンパイル使用メモリ 275,940 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-08-16 22:22:52
合計ジャッジ時間 9,097 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 15 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 56 ms
5,376 KB
testcase_08 AC 12 ms
5,376 KB
testcase_09 AC 6 ms
5,376 KB
testcase_10 AC 7 ms
5,376 KB
testcase_11 AC 124 ms
5,376 KB
testcase_12 AC 13 ms
5,376 KB
testcase_13 AC 6 ms
5,376 KB
testcase_14 AC 143 ms
5,376 KB
testcase_15 AC 36 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 19 ms
5,376 KB
testcase_18 AC 5 ms
5,376 KB
testcase_19 AC 20 ms
5,376 KB
testcase_20 AC 187 ms
5,376 KB
testcase_21 AC 171 ms
5,376 KB
testcase_22 AC 188 ms
5,376 KB
testcase_23 AC 142 ms
5,376 KB
testcase_24 AC 174 ms
5,376 KB
testcase_25 AC 204 ms
5,376 KB
testcase_26 AC 212 ms
5,376 KB
testcase_27 AC 208 ms
5,376 KB
testcase_28 AC 208 ms
5,376 KB
testcase_29 AC 182 ms
5,376 KB
testcase_30 AC 6 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 6 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 3 ms
5,376 KB
testcase_37 AC 1 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 176 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#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