結果

問題 No.980 Fibonacci Convolution Hard
コンテスト
ユーザー aogera
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0