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 |
|
|
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 |