记录编号 |
377246 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HZOI 2015] 释迦 |
最终得分 |
100 |
用户昵称 |
MistyEye |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
1.763 s |
提交时间 |
2017-03-01 06:30:39 |
内存使用 |
58.31 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define ld long double
#define ll long long
const int maxn = (1<<18)+5;
const int mod = 23333333, M = 4830;
namespace FFT {
const ld Pi = acos(-1.0);
struct Complex {
ld x, y;
Complex(ld x=0.0, ld y=0.0) : x(x), y(y) {}
Complex operator + (const Complex &a) { return Complex(x+a.x, y+a.y); }
Complex operator - (const Complex& a) { return Complex(x-a.x, y-a.y); }
Complex operator * (const Complex& a) { return Complex(x*a.x-y*a.y, x*a.y+y*a.x); }
Complex operator * (const ld &a) { return Complex(x*a, y*a); }
Complex operator / (const ld &a) { return Complex(x/a, y/a); }
Complex conj(bool c=1) { return Complex(x, c?-y:y);}
} w[maxn];
Complex a0[maxn], b0[maxn], a1[maxn], b1[maxn];
Complex c0[maxn], c1[maxn], c2[maxn];
int n, rev[maxn];
void FFT_init(int N) {
int l = 0;
for(n=1; n<N; n<<=1, ++l); --l;
for(int i=0; i<n; ++i) {
w[i] = Complex(cos(2*Pi*i/n), sin(2*Pi*i/n));
if(i) rev[i] = rev[i>>1]>>1|((i&1)<<l);
}
}
void FFT(Complex *a, int op) {
for(int i=1; i<n; ++i) if(rev[i]>i) swap(a[rev[i]], a[i]);
for(int k=2; k<=n; k<<=1)
for(int j=0; j<n; j+=k)
for(int i=0; i<(k>>1); ++i) {
Complex t = a[i+j+(k>>1)]*w[n/k*i].conj(op);
a[i+j+(k>>1)] = a[i+j]-t;
a[i+j] = a[i+j]+t;
}
if(op) for(int i=0; i<n; ++i) a[i].x /= n;
}
void FFT(Complex *a, Complex *b) {
static Complex t[maxn];
for(int i=0; i<n; ++i) t[i] = Complex(a[i].x, b[i].x);
FFT(t, 0);
for(int i=0; i<n; ++i) {
int j = (n-i)&(n-1);
a[i] = (t[i]+t[j].conj())*Complex(0.5, 0);
b[i] = (t[i]-t[j].conj())*Complex(0, -0.5);
}
}
void mul(int *a, int *b, int *c, int N) {
for(int i=0; i<n; ++i) a0[i] = Complex(a[i]/M), b0[i] = Complex(a[i]%M);
for(int i=0; i<n; ++i) a1[i] = Complex(b[i]/M), b1[i] = Complex(b[i]%M);
FFT(a0, b0); FFT(a1, b1);
for(int i=0; i<n; ++i) {
c0[i] = a0[i]*a1[i];
c1[i] = a0[i]*b1[i]+a1[i]*b0[i];
c2[i] = b0[i]*b1[i];
}
FFT(c0, 1); FFT(c1, 1); FFT(c2, 1);
for(int i=0; i<N; ++i) {
ll x = (ll)round(c0[i].x);
ll y = (ll)round(c1[i].x);
ll z = (ll)round(c2[i].x);
c[i] = (x*M%mod*M%mod+y*M%mod+z)%mod;
}
}
}
int N, x[maxn], y[maxn], ans[maxn];
int main() {
freopen("annona_squamosa.in","r",stdin);
freopen("annona_squamosa.out","w",stdout);
scanf("%d", &N);
for(int i=0; i<N; ++i) scanf("%d", x+i);
for(int i=0; i<N; ++i) scanf("%d", y+i);
FFT::FFT_init(N+N);
FFT::mul(x, y, ans, N);
for(int i=0; i<N; ++i) printf("%d ", ans[i]); puts("");
getchar(), getchar();
return 0;
}