結果

問題 No.931 Multiplicative Convolution
ユーザー RubikunRubikun
提出日時 2019-11-23 04:10:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,696 bytes
コンパイル時間 1,989 ms
コンパイル使用メモリ 183,148 KB
実行使用メモリ 51,232 KB
最終ジャッジ日時 2024-10-11 06:46:26
合計ジャッジ時間 7,898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 372 ms
48,228 KB
testcase_10 WA -
testcase_11 AC 401 ms
49,328 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=100005,INF=1<<30;
int P;
vector<complex<long double>> fft(vector<complex<long double>> 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*=2){
        for(int j=0;j<b;j++){
            complex<long double> w;
            if(inverse==1) w=polar(1.0,(2*M_PI)/(2*b)*j*1);
            else w=polar(1.0,(2*M_PI)/(2*b)*j*(-1));
            
            for(int k=0;k<n;k+=b*2){
                complex<long double> s=a[j+k];
                complex<long double> 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]/=n;
    return a;
}

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

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


int main(){

    cin>>P;
    vector<long double> A(P),B(P);
    for(int i=0;i<P-1;i++) cin>>A[i+1];
    for(int i=0;i<P-1;i++) cin>>B[i+1];
    
    int root=1;
    for(root;;root++){
        set<int> SE;
        int now=1;
        bool ok=true;
        for(int i=1;i<=P-1;i++){
            now*=root;
            now%=P;
            if(SE.find(now)!=SE.end()){
                ok=false;
                break;
            }
            SE.insert(now);
        }
        if(ok) break;
    }
    
    vector<long double> a(P),b(P);
    int now=1;
    for(int i=1;i<P;i++){
        now*=root;
        now%=P;
        a[i]=A[now];
        b[i]=B[now];
    }
    
    vector<long double> res=convolve(a,b);
    
    vector<ll> ans(P-1),tr(P-1);
    for(int i=0;i<res.size();i++){
        ans[i%(P-1)]+=ll(res[i]+0.5);
        ans[i%(P-1)]%=mod;
    }
    now=1;
    for(int i=1;i<P;i++){
        tr[now-1]=ans[i-1];
        now*=root;
        now%=P;
    }
    for(int i=0;i<tr.size();i++) cout<<tr[i]<<" ";
    cout<<endl;
    
    //cout<<root<<endl;
}
0