結果
問題 |
No.980 Fibonacci Convolution Hard
|
ユーザー |
|
提出日時 | 2025-08-12 16:46:02 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 385 ms / 2,000 ms |
コード長 | 1,844 bytes |
コンパイル時間 | 5,595 ms |
コンパイル使用メモリ | 335,196 KB |
実行使用メモリ | 20,480 KB |
最終ジャッジ日時 | 2025-08-12 16:46:18 |
合計ジャッジ時間 | 14,775 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using ld=long double; using pl=pair<ll,ll>; using vpl=vector<pl>; using vl=vector<ll>; using vvl=vector<vl>; long double pi=atan2(0,-1); #define rep(i,n) for(long long i=0LL;i<n;i++) #define rrep(i,a,b) for(long long i=a;i>=b;i--) #define REP1(i,k,n) for(long long i=k;i<n;i++) #define REP2(i,k,n,d) for(long long i=k;i<n;i+=d) #define overload4(a, b, c, d, e, ...) e #define FOR(...) overload4(__VA_ARGS__, REP2,REP1)(__VA_ARGS__) #define ALL(v) v.begin(),v.end() template<typename S,typename T>ostream&operator<<(ostream& os,pair<S,T>& v){os <<'{'<<v.first<<','<<v.second<<'}';return os;} template<typename T>ostream&operator<<(ostream& os,vector<T>&v){for(int i = 0;i < size(v);i++)os << v[i] << (i+1==size(v)?"":" ");return os;} template<typename T>istream&operator>>(istream& is,vector<T>&v){for(auto &in : v)is >> in;return is;} ll INF = 1152921504606846976; /* INF = 1LL << 60 */ //using mint = modint998244353;ll MOD = 998244353; using mint = modint1000000007;ll MOD = 1000000007; // using mint = modint; using vm = vector<mint>; using vvm = vector<vm>; vl dx = {1,0,-1,0}, dy = {0,-1,0,1}; //---------------------------------------------- #define Q_MAX 2000009 int main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15); //============================================== ll P,Q; cin>>P>>Q; vm A(Q_MAX); vm B(Q_MAX); A[1] = 0; A[2] = 1; rep(i,10){ A[i+3] = P*A[i+2]+A[i+1]; } FOR(i,1,10) FOR(s,1,10) FOR(t,1,10) if(s + t == i) B[i]+=A[s]*A[t]; ll p = P; FOR(i,5,Q_MAX){ B[i] = 2*p*B[i-1] - (p*p-2)*B[i-2] -(2*p)*B[i-3]-B[i-4]; } vl ans(Q); rep(qi,Q){ ll q; cin>>q; ans[qi] = B[q].val(); } rep(i,Q) cout << ans[i] << endl; }