Back to : algorithms
Contents

νμ΄

κ²°κ΅­ λ¬Έμ μ μμ μ, μ / μ€κ°/ μλλ₯Ό $u_i, m_i, l_i$ λΌκ³  ν  λ, $u_i + l_j = 2m_k$ μΈ μμμ $(i, j, k)$μ κ°μλ₯Ό μΈλ λ¬Έμ μ΄λ€.

μ΄ λ¬Έμ λ λ§€μ° μ μλ €μ§ Convolution λ¬Έμ λ‘, μμ΄μ μΉ΄μ΄ν λ€ν­μμΌλ‘ μΈμ½λ©νλ©΄ μ½κ² ν μ μλ€. μμ΄μ΄ 1, 3, 4, 5, 5λ©΄ $x + x^3 + x^4 + 2x^5$ μΈ μμΌλ‘. μ΄λ κ² μΈμ½λ©ν΄μ $u(x), m(x), l(x)$ λ₯Ό λ§λ  λ€μ,

$u(x)l(x)$μ κ³μ°νλ©΄ κ·Έ $n$μ°¨ν­μ κ³μκ° $u_i + l_j = n$ μΈ μμμ $i, j$ μ κ°μκ° λλ€. λ°λΌμ, κ° $n$μ λν΄, $m_k = n$μΈ $k$μ κ°μμ $u(x)l(x)$μ $2n$μ°¨ ν­μ κ³μλ₯Ό κ³±ν΄μ λνλ©΄ κ·Έλλ‘ κ΅¬νλ λ΅μ΄ λκ³ , μ΄λ₯Ό FFTλ₯Ό μ΄μ©νμ¬ $O(n \log n)$μ κ΅¬ν  μ μμμ΄ μ μλ €μ Έ μλ€.

μ¬λ΄μΌλ‘β¦ ICPC μμΈ λ¦¬μ λμ μ΄λ° Do you know *** λ¬Έμ κ° κ½€ λ§μ΄ λμ€λ νΈμΈ κ² κ°λ€. 2017 FFT, 2017 μΈμ FFT, 2019 μΈμ LiChaoTree / LR Flow β¦

μ½λ

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

#define sz(v) ((int)(v).size())
typedef vector<int> vi;
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 vi &a,const vi &b,vi &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));
}

vi u(121212, 0), m(121212, 0), l(121212, 0), c;

void input(vi &v)
{
int n; cin >> n;
for (int i = 0; i < n; i++)
{
int x; cin >> x;
v[x+30000]++;
}
}

int32_t main()
{
usecppio
input(u); input(m); input(l);
multiply(u, l, c);
int ans = 0;
for (int i = 0; i <= 60000; i++)
ans += m[i] * c[2*i];
cout << ans << '\n';
}