Submission #1438729
Source Code Expand
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl
using namespace std;
typedef pair<int,int>P;
typedef complex<double>C;
const int MAX_N = 100005;
const double PI = 4*atan(1.0);
vector<C> FFT(double theta, const vector<C>& a){
int n = (int)a.size();
vector<C> ret = a;
for(int m=n; m>=2; m>>=1){
int mh = m>>1;
rep(i,mh){
C w = exp(i*theta*C(0,1));
for(int j=i; j<n; j+=m){
int k = j+mh;
C x = ret[j] - ret[k];
ret[j] += ret[k];
ret[k] = w*x;
}
}
theta *= 2;
}
int i=0;
for(int j=1; j<n-1; j++){
for(int k=n>>1; k>(i^=k); k>>= 1){
}
if(j < i) swap(ret[i], ret[j]);
}
return ret;
}
//畳み込み
template<class T>
vector<T> Convolution(const vector<T> &lhs, const vector<T> &rhs){
int n = 1;
while(n < (int)max(lhs.size(), rhs.size())*2){
n <<= 1;
}
vector<C> temp1(n);
vector<C> temp2(n);
for(int i=0; i<n/2; i++){
if(i < (int)lhs.size()){
temp1[i] = C(lhs[i], 0);
}
if(i < (int)rhs.size()){
temp2[i] = C(rhs[i], 0);
}
}
//FFTにかけて周波数分解
temp1 = FFT(2.0*PI/n, temp1);
temp2 = FFT(2.0*PI/n, temp2);
//周波数同士で掛け算
rep(i,n){
temp1[i] *= temp2[i];
}
//逆FFTをかけて元に戻す
temp1 = FFT(-2.0*PI/n, temp1);
vector<T> ret(n);
rep(i,n){
ret[i] = (T)(temp1[i].real()/n + 0.5); //T=intの時用
}
return ret;
}
int main()
{
int n;
cin >> n;
vector<int> a(n),b(n);
rep(i,n){
scanf("%d%d",&a[i],&b[i]);
}
vector<int> res = Convolution(a,b);
cout << 0 << endl;
rep(i,2*n-1){
cout << res[i] << endl;
}
}
Submission Info
Submission Time
2017-07-19 21:14:30+0900
Task
C - 高速フーリエ変換
User
kopricky
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
2418 Byte
Status
AC
Exec Time
483 ms
Memory
13312 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:90:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i],&b[i]);
^
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
6 ms
768 KB
01_00_01
AC
1 ms
256 KB
01_01_19
AC
1 ms
256 KB
01_02_31
AC
1 ms
256 KB
01_03_22
AC
1 ms
256 KB
01_04_31
AC
1 ms
256 KB
01_05_40
AC
1 ms
256 KB
01_06_15
AC
1 ms
256 KB
01_07_39
AC
1 ms
256 KB
01_08_28
AC
1 ms
256 KB
01_09_30
AC
1 ms
256 KB
01_10_23
AC
1 ms
256 KB
01_11_33
AC
1 ms
256 KB
01_12_11
AC
1 ms
256 KB
01_13_28
AC
1 ms
256 KB
01_14_41
AC
1 ms
256 KB
01_15_26
AC
1 ms
256 KB
01_16_49
AC
1 ms
256 KB
01_17_34
AC
1 ms
256 KB
01_18_02
AC
1 ms
256 KB
01_19_33
AC
1 ms
256 KB
01_20_29
AC
1 ms
256 KB
02_00_51254
AC
237 ms
6812 KB
02_01_82431
AC
410 ms
13184 KB
02_02_17056
AC
89 ms
3456 KB
02_03_34866
AC
183 ms
6656 KB
02_04_6779
AC
31 ms
1024 KB
02_05_65534
AC
288 ms
6912 KB
02_06_65535
AC
280 ms
6912 KB
02_07_65536
AC
284 ms
6912 KB
02_08_65537
AC
357 ms
13056 KB
02_09_65538
AC
358 ms
13056 KB
02_10_100000
AC
483 ms
13312 KB