結果
問題 |
No.3228 Very Large Fibonacci Sum
|
ユーザー |
![]() |
提出日時 | 2025-08-08 23:47:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,023 bytes |
コンパイル時間 | 4,067 ms |
コンパイル使用メモリ | 316,804 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-08 23:47:36 |
合計ジャッジ時間 | 7,476 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/convolution> using namespace atcoder; using mint = modint1000000007; using ll = long long; 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 = convolution(f, g_), t = convolution(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 = convolution(q,y); cout << BostanMori(x, y, n).val() + BostanMori(p, q, n).val() << '\n'; return 0; }