풀이
.
코드
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cmath>
#include <complex>
#include <vector>
#include <algorithm>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
typedef complex<double> base;
void fft(vector<base> &a, bool invert) {
int n = sz(a);
for (int i=1,j=0;i<n;i++){
int bit = n >> 1;
for (;j>=bit;bit>>=1) j -= bit;
j += bit;
if (i < j) swap(a[i],a[j]);
}
for (int len=2;len<=n;len<<=1){
double ang = 2*M_PI/len*(invert?-1:1);
base wlen(cos(ang),sin(ang));
for (int i=0;i<n;i+=len){
base w(1);
for (int j=0;j<len/2;j++){
base u = a[i+j], v = a[i+j+len/2]*w;
a[i+j] = u+v;
a[i+j+len/2] = u-v;
w *= wlen;
}
}
}
if (invert) {
for (int i=0;i<n;i++) a[i] /= n;
}
}
void multiply(const vector<int> &a,const vector<int> &b,vector<int> &res) {
vector <base> fa(all(a)), fb(all(b));
int n = 1;
while (n < max(sz(a),sz(b))) n <<= 1;
fa.resize(n); fb.resize(n);
fft(fa,false); fft(fb,false);
for (int i=0;i<n;i++) fa[i] *= fb[i];
fft(fa,true);
res.resize(n);
for (int i=0;i<n;i++) res[i] = int(fa[i].real()+(fa[i].real()>0?0.5:-0.5));
}
int main() {
int n;
vector<int> a, b, res;
scanf("%d", &n);
a.resize(n*2); b.resize(n);
for (int i=0;i<n;i++) {
scanf("%d", &a[i]);
a[i+n] = a[i];
}
for (int i=0;i<n;i++) {
scanf("%d", &b[n-i-1]);
}
multiply(a, b, res);
int ans = 0;
for (int i=n;i<n*2;i++) {
ans = max(ans, res[i]);
}
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이