oj.uz

Submission #200853

# Submission time Handle Problem Language Result Execution time Memory
200853 2020-02-08T10:13:39 Z jh05013 씽크스몰 (kriii3_TT) C++17
20 / 30
 1605 ms 75244 KB 
#include <bits/stdc++.h>
#define sz(X) (int)((X).size())
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL);ios_base::sync_with_stdio(false);}
template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;}
template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){for(auto&y:x)os<<y<<" ";return os;}

const double PI = acos(-1);
typedef complex<long double> CD;
typedef vector<CD> VCD;
typedef vector<ll> poly;
void FFT(VCD &A, bool inv){
    int n = A.size();
    for(int i=1, j=0; i<n; i++){
        for(int k=n>>1; (j^=k)<k; k>>= 1);
        if(i < j) swap(A[i], A[j]);
    }
    for(int i=1; i<n; i<<= 1){
        double w = PI / i;
        if(inv) w = -w;
        CD x(cos(w), sin(w));
        for(int j=0; j<n; j+= i<<1){
            CD y(1);
            for(int k=0; k<i; k++){
                CD z = A[i+j+k]*y;
                A[i+j+k] = A[j+k]-z, A[j+k]+= z;
                y*= x;
            }
        }
    }
    if(inv) for(int i=0; i<n; i++) A[i]/= n;
}

poly multiply(poly X, poly Y){
    int n, xy = X.size()+Y.size();
    for(n=1; n<xy; n<<= 1);
    VCD A(n), B(n);
    for(size_t i=0; i<X.size(); i++) A[i] = X[i];
    for(size_t i=0; i<Y.size(); i++) B[i] = Y[i];
    FFT(A, 0), FFT(B, 0);
    for(int i=0; i<n; i++) A[i]*= B[i];
    FFT(A, 1);
    poly res(xy);
    for(int i=0; i<xy; i++) res[i] = A[i].real();
    return res;
}

/* Kriiicon Thinksmall: precise multiplication */

poly thinksmall(poly X, poly Y){
    int N = 2; while(N < sz(X)+sz(Y)) N<<= 1;
    VCD A(N), B(N), AR(N), BR(N);
    
    for(int i=0; i<sz(X); i++) A[i] = CD(X[i]>>15, X[i]&32767);
    for(int i=0; i<sz(Y); i++) B[i] = CD(Y[i]>>15, Y[i]&32767);
    FFT(A, 0); FFT(B, 0);
    for(int i=0; i<N; i++){
        int j = i? N-i : i;
        CD f1 = (A[i] + conj(A[j])) / CD(2, 0),
           f2 = (A[i] - conj(A[j])) / CD(0, 2),
           f3 = (B[i] + conj(B[j])) / CD(2, 0),
           f4 = (B[i] - conj(B[j])) / CD(0, 2);
        AR[i] = f1 * (f3 + f4 * CD(0, 1));
        BR[i] = f2 * (f3 + f4 * CD(0, 1));
    }
    FFT(AR, 1); FFT(BR, 1);
    vector<ll> ans;
    for(int i=0; i<N; i++){
        ll ar = roundl(real(AR[i])),
           ai = roundl(imag(AR[i])),
           br = roundl(real(BR[i])),
           bi = roundl(imag(BR[i]));
        ll res = bi + ((ai + br) << 15) + (ar << 30);
        ans.push_back(res);
    }
    return ans;
}

int main(){OJize();
    int n, m; cin>>n>>m;
    poly X(n+1), Y(m+1);
    for(int i=0; i<=n; i++) cin>>X[i];
    for(int i=0; i<=m; i++) cin>>Y[i];
    ll ans = 0;
    for(ll x: thinksmall(X, Y)) ans^= x;
    cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 9 ms 632 KB Output is correct
6 Correct 9 ms 632 KB Output is correct
7 Correct 9 ms 632 KB Output is correct
8 Correct 9 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 5240 KB Output is correct
2 Correct 359 ms 19568 KB Output is correct
3 Correct 338 ms 19956 KB Output is correct
4 Correct 736 ms 38128 KB Output is correct
5 Correct 769 ms 38384 KB Output is correct
6 Correct 716 ms 38132 KB Output is correct
7 Correct 705 ms 38640 KB Output is correct
8 Correct 722 ms 38640 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1605 ms 75244 KB Output isn't correct
2 Halted 0 ms 0 KB -