結果
問題 |
No.3228 Very Large Fibonacci Sum
|
ユーザー |
![]() |
提出日時 | 2025-08-09 00:17:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,215 bytes |
コンパイル時間 | 3,724 ms |
コンパイル使用メモリ | 313,092 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-09 00:17:35 |
合計ジャッジ時間 | 4,955 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/convolution> using namespace atcoder; using mint = modint1000000007; using ll = long long; #define rep(i, n) for(int i = 0; i < n; ++i) vector<mint> cv(vector<mint> a, vector<mint> b){ int n = a.size(), m = b.size(); vector<mint> res(n+m-1,0); rep(i,n)rep(j,m) res[i+j] += a[i]*b[j]; return res; } mint BostanMori(vector<mint> f, vector<mint> g, ll k){ vector<mint> g_, s, t; int m; while(k){ m = g.size(); g_ = g; for(int i=1;i<m;i+=2) g_[i] = -g_[i]; s = cv(f, g_), t = cv(g, g_); f.resize(min<ll>(k+1, (s.size()+1-(k&1))>>1)); g.resize(min<ll>(k+1, (t.size()+1)>>1)); for(int i=k&1;i<(int)s.size()&&((i>>1)<=k);i+=2) f[i>>1] = s[i]; for(int i=0;i<(int)t.size()&&((i>>1)<=k);i+=2) g[i>>1] = t[i]; k >>= 1; } return f[0] / g[0]; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll a,b,c,d,e,n; cin >> a >> b >> c >> d >> e >> n; vector<mint> x = {a,b-c*a}, y = {1, -c-1, -d+c, d}, p = {0,0,e}, q = {1,-1}; q = cv(q,y); cout << (BostanMori(x, y, n) + BostanMori(p, q, n)).val() << '\n'; return 0; }