結果
問題 | No.2883 K-powered Sum of Fibonacci |
ユーザー |
![]() |
提出日時 | 2024-07-29 20:48:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#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 longusing 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 = 0mat z(K+2, vector<mint>(1, 0));z[0][0] = 1;mat ans = mul(Mpow, z);cout << ans[K+1][0].val() << endl;}