Submission #7469644
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 zip(v) sort(all(v)),v.erase(unique(all(v)),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
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
using namespace std;
typedef pair<int,int>P;
complex<double> operator* (const complex<double> a, const complex<double> b){
return complex<double>(a.real()*b.real()-a.imag()*b.imag(),a.real()*b.imag()+a.imag()*b.real());
}
vector<complex<double> > fft(vector<complex<double> > a,bool rev = false)
{
constexpr double PI = std::acos(-1);
int n = a.size(),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 i = 1; i < n; i *= 2) {
for(int j = 0; j < i; j++){
complex<double> w = {cos(2*PI/(i*2)*(rev?-1:1)*j), sin(2*PI/(i*2)*(rev?-1:1)*j)};
for(int k = 0; k < n; k += i * 2) {
complex<double> s = a[j+k];
complex<double> t = a[j+k+i]*w;
a[j+k+0] = s+t;
a[j+k+i] = s-t;
}
}
}
if(rev){
for(int i = 0; i < n; i++){
a[i] /= n;
}
}
return a;
}
vector<int> mul(vector<int> a, vector<int> b)
{
int s = (int)a.size() + (int)b.size() - 1,t = 1;
while (t < s) t *= 2;
vector<complex<double> > A(t), B(t);
for(int i = 0; i < (int)a.size(); i++){
A[i].real(a[i]);
}
for(int i = 0; i < (int)b.size(); i++){
B[i].real(b[i]);
}
A = fft(A), B = fft(B);
for(int i = 0; i < t; i++){
A[i] *= B[i];
}
A = fft(A, true);
a.resize(s);
//整数に直す
for(int i = 0; i < s; i++){
a[i] = round(A[i].real());
}
return a;
}
int main()
{
int n;
scanf("%d",&n);
vector<int> a(n+1,0),b(n+1,0);
rep(i,n){
scanf("%d%d",&a[i+1],&b[i+1]);
}
a = mul(a,b);
rep(i,2*n){
cout << a[i+1] << "\n";
}
return 0;
}
Submission Info
Submission Time
2019-09-12 07:12:07+0900
Task
C - 高速フーリエ変換
User
kopricky
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
2675 Byte
Status
AC
Exec Time
174 ms
Memory
14080 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:85:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:88:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i+1],&b[i+1]);
^
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
5 ms
512 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
84 ms
7168 KB
02_01_82431
AC
164 ms
13824 KB
02_02_17056
AC
38 ms
3584 KB
02_03_34866
AC
80 ms
6912 KB
02_04_6779
AC
10 ms
1152 KB
02_05_65534
AC
90 ms
7424 KB
02_06_65535
AC
90 ms
7424 KB
02_07_65536
AC
161 ms
13568 KB
02_08_65537
AC
163 ms
13568 KB
02_09_65538
AC
162 ms
13568 KB
02_10_100000
AC
174 ms
14080 KB