結果

問題 No.980 Fibonacci Convolution Hard
ユーザー RubikunRubikun
提出日時 2020-01-31 22:05:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,485 bytes
コンパイル時間 1,888 ms
コンパイル使用メモリ 176,308 KB
実行使用メモリ 208,960 KB
最終ジャッジ日時 2023-10-17 09:54:13
合計ジャッジ時間 9,082 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_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