oj.uz

Submission #222020

# Submission time Handle Problem Language Result Execution time Memory
222020 2020-04-11T21:21:32 Z jhnah917 씽크스몰 (kriii3_TT) C++14
0 / 30
 296 ms 44396 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef complex<double> base;
typedef vector<ll> poly;
const double PI = acos(-1);
void FFT(vector<base> &f, bool inv = 0){
    int n = f.size(), j = 0;
    for(int i=1; i<n; i++){
        for(int k=(n>>1); (j^=k)<k; k >>= 1);
        if(i < j) swap(f[i], f[j]);
    }
    double ang = 2 * PI / n; if(inv) ang *= -1;
    vector<base> root(n/2);
    for(int i=0; i<n/2; i++)
        root[i] = base(cos(ang*i), sin(ang*i));
    for(int i=2; i<=n; i<<= 1){
        int step = n/i;
        for(int j=0; j<n; j+=i) for(int k=0; k<i/2; k++){
            base u = f[j+k], v = f[j+k+i/2] * root[step*k];
            f[j+k] = u+v, f[j+k+i/2] = u-v;
        }
    }
    if(inv) for(int i=0; i<n; i++) f[i] /= n;
}
vector<ll> mul(vector<ll> a, vector<ll> b){
    int n = 2; while(n < a.size() + b.size()) n <<= 1;
    vector<base> A(n), B(n), AR(n), BR(n);
    
    for(int i=0; i<a.size(); i++) A[i] = base(a[i]>>15, a[i]&32767);
    for(int i=0; i<b.size(); i++) B[i] = base(b[i]>>15, b[i]&32767);
    FFT(A); FFT(B);
    for(int i=0; i<n; i++){
        int j = i? n-i : i;
        auto f1 = (A[i] + conj(A[j])) / base(2, 0);
        auto f2 = (A[i] - conj(A[j])) / base(0, 2);
        auto f3 = (B[i] + conj(B[j])) / base(2, 0);
        auto f4 = (B[i] - conj(B[j])) / base(0, 2);
        AR[i] = f1 * (f3 + f4 * base(0, 1));
        BR[i] = f2 * (f3 + f4 * base(0, 1));
    }
    FFT(AR, 1); FFT(BR, 1);
    vector<ll> ans(n);
    for(int i=0; i<n; i++){
        ll ar = roundl(real(AR[i]));
        ll ai = roundl(imag(AR[i]));
        ll br = roundl(real(BR[i]));
        ll bi = roundl(imag(BR[i]));
        ans[i] = bi + ((ai + br) << 15) + (ar << 30);
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<ll> a(n+1), b(n+1);
    for(auto &i : a) cin >> i;
    for(auto &i : b) cin >> i;
    auto res = mul(a, b);
    ll ans = 0;
    for(auto i : res) ans ^= i;
    cout << ans;
}

Compilation message

tt.cpp: In function 'std::vector<long long int> mul(std::vector<long long int>, std::vector<long long int>)':
tt.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int n = 2; while(n < a.size() + b.size()) n <<= 1;
                      ~~^~~~~~~~~~~~~~~~~~~~~
tt.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) A[i] = base(a[i]>>15, a[i]&32767);
                  ~^~~~~~~~~
tt.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<b.size(); i++) B[i] = base(b[i]>>15, b[i]&32767);
                  ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3072 KB Output is correct
2 Incorrect 17 ms 3120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 43512 KB Output is correct
2 Incorrect 296 ms 44396 KB Output isn't correct
3 Halted 0 ms 0 KB -