結果

問題 No.980 Fibonacci Convolution Hard
コンテスト
ユーザー Rubikun
提出日時 2020-01-31 22:05:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,485 bytes
コンパイル時間 1,841 ms
コンパイル使用メモリ 175,268 KB
実行使用メモリ 276,204 KB
最終ジャッジ日時 2024-09-17 08:21:53
合計ジャッジ時間 8,740 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<30;

struct C{
    double x;
    double y;
    
    C operator + (const C &other)const{
        return {x+other.x , y+other.y};
    };
    
    C operator - (const C &other)const{
        return {x-other.x , y-other.y};
    };
    
    C operator * (const C &other)const{
        return {x*other.x-y*other.y , x*other.y+y*other.x};
    };
    
};

vector<C> fft(vector<C> &a,bool inverse){//inverse==1のとき逆変換
    int n=a.size();
    int h=0;
    for(int i=0;(1<<i)<n;i++) h++;
    
    for(int i=0;i<n;i++){
        int j=0;
        for(int k=0;k<h;k++) j|=((i>>k)&1)<<(h-1-k);
        if(i<j) swap(a[i],a[j]);
    }
    
    for(int b=1;b<n;b<<=1){
        for(int j=0;j<b;j++){
            C w;
            if(inverse==1){
                double re=cos((2*M_PI)/(2*b)*j*1),im=sin((2*M_PI)/(2*b)*j*1);
                w=C{re,im};
            }else{
                double re=cos((2*M_PI)/(2*b)*j*(-1)),im=sin((2*M_PI)/(2*b)*j*(-1));
                w=C{re,im};
            }
            
            for(int k=0;k<n;k+=b*2){
                C s=a[j+k];
                C t=a[j+k+b]*w;
                a[j+k]=s+t;
                a[j+k+b]=s-t;
            }
        }
    }
    
    if(inverse) for(int i=0;i<n;i++){
        a[i].x/=n;
        a[i].y/=n;
    }
    return a;
}

vector<C> fft(vector<double> &a,bool inverse){//オーバーロード
    
    vector<C> a_complex(a.size());
    for(int i=0;i<a.size();i++) a_complex[i]=C{a[i],0};
    return fft(a_complex,inverse);
}

vector<double> convolve(vector<double> &a,vector<double> &b){//解く
    
    int s=a.size()+b.size()-1;
    int t=1;
    while(t<s) t*=2;
    
    a.resize(t);
    b.resize(t);
    
    vector<C> A=fft(a,0),B=fft(b,0);
    for(int i=0;i<t;i++) A[i]=A[i]*B[i];
    
    A=fft(A,1);
    a.resize(s);
    for(int i=0;i<s;i++) a[i]=A[i].x;
    return a;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll P,Q;cin>>P>>Q;
    vector<double> A(2000001,0.0),B(2000001,0.0);
    A[2]=1.0;
    B[2]=1.0;
    
    for(int i=3;i<=2000000;i++){
        ll k=(ll(A[i-1])*P+ll(A[i-2]))%mod;
        A[i]=k;
        B[i]=k;
    }
    
    vector<double> ans=convolve(A,B);
    
    while(Q--){
        int a;cin>>a;
        cout<<int(ans[a]+0.5)<<endl;
    }
}
0