Submission #7972718


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
//#define MOD 1000000007
#define MOD 998244353
#define INF 1145141919810893364
#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

int BE(int b,int e){
    int r=1;
    while(e){
        if(e&1){
            r=(r*b)%MOD;
        }
        b=(b*b)%MOD;
        e >>=1;
    }
    return r;
}

vector<int> DFT_int(vector<int> A){
    int N=A.size();
    if(N==1)return A;
    vector<int> A0(N/2),A1(N/2),iA0,iA1,iA(N);
    for(int i=0;i<N;i++){
        if(i%2==0){
            A0[i/2]=A[i];
        }else{
            A1[i/2]=A[i];
        }
    }
    iA0=DFT_int(A0);
    iA1=DFT_int(A1);
    
    int omega=BE(3,(MOD-1)/N);//3は原始根 MODに依存する
    int ith_zeta = 1;
    for(int i=0;i<N;i++){
        iA[i]=(iA0[i%(N/2)]+ ith_zeta*iA1[i%(N/2)])%MOD;
        ith_zeta = (ith_zeta*omega)%MOD;
    }
    return iA;
}

vector<int> iDFT_int(vector<int> iA){
    int N=iA.size();
    int N_inverse = BE(N,MOD-2);
    vector<int> A,dA,rA;
    dA=DFT_int(iA);
    for(int i=0;i<N;i++){
        rA.push_back(dA[(N-i)%N]);
        A.push_back((rA[i]*N_inverse)%MOD);
    }
    return A;
}

vector<int> convolution_int(vector<int> A,vector<int> B){
    int deg = A.size() + B.size() -1;
    int N=1;
    while(N<deg){N<<=1;}
    A.resize(N);B.resize(N);
    vector<int> C(N),iC(N),iA,iB;
    iA=DFT_int(A);iB=DFT_int(B);
    for(int i=0;i<N;i++){
        iC[i]=(iA[i]*iB[i])%MOD;
    }
    C=iDFT_int(iC);
    C.resize(deg);
    return C;
}
 
signed main(void){
    ios::sync_with_stdio(false), cin.tie(0);
    
    int N;
    vector<int> A,B;
    cin >> N;
    int a;
    REP(i,N){
        cin >> a;
        A.push_back(a%MOD);
        cin >> a;
        B.push_back(a%MOD);
    }
    vector<int> C = convolution_int(A,B);
    cout << 0;
    REP(i,2*N-1){
        cout << endl << C[i];
    }
    
    return 0;
}

Submission Info

Submission Time
Task C - 高速フーリエ変換
User x0214sh7
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2259 Byte
Status AC
Exec Time 820 ms
Memory 30492 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 33
Set Name Test Cases
Sample 00_sample_01
All 00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000
Case Name Status Exec Time Memory
00_sample_01 AC 1 ms 256 KB
01_00_01 AC 1 ms 256 KB
01_01_19 AC 2 ms 256 KB
01_02_31 AC 2 ms 256 KB
01_03_22 AC 1 ms 256 KB
01_04_31 AC 2 ms 256 KB
01_05_40 AC 2 ms 256 KB
01_06_15 AC 1 ms 256 KB
01_07_39 AC 2 ms 256 KB
01_08_28 AC 2 ms 256 KB
01_09_30 AC 2 ms 256 KB
01_10_23 AC 1 ms 256 KB
01_11_33 AC 2 ms 256 KB
01_12_11 AC 1 ms 256 KB
01_13_28 AC 2 ms 256 KB
01_14_41 AC 2 ms 256 KB
01_15_26 AC 2 ms 256 KB
01_16_49 AC 2 ms 256 KB
01_17_34 AC 2 ms 256 KB
01_18_02 AC 1 ms 256 KB
01_19_33 AC 2 ms 256 KB
01_20_29 AC 2 ms 256 KB
02_00_51254 AC 402 ms 15388 KB
02_01_82431 AC 769 ms 30252 KB
02_02_17056 AC 174 ms 7744 KB
02_03_34866 AC 358 ms 15124 KB
02_04_6779 AC 50 ms 2208 KB
02_05_65534 AC 450 ms 15700 KB
02_06_65535 AC 461 ms 15692 KB
02_07_65536 AC 455 ms 15692 KB
02_08_65537 AC 735 ms 30004 KB
02_09_65538 AC 711 ms 30004 KB
02_10_100000 AC 820 ms 30492 KB