oj.uz

Submission #222017

# Submission time Handle Problem Language Result Execution time Memory
222017 2020-04-11T21:12:19 Z jhnah917 씽크스몰 (kriii3_TT) C++14
0 / 30
 330 ms 47536 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef vector<ll> poly;
typedef complex<double> base;
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 >> 1);
    for(int i=0; i<root.size(); i++) root[i] = base(cos(ang * i), sin(ang * i));
    for(int i=2; i<=n; i<<=1){
        int st = n / i;
        for(int j=0; j<n; j+=i) for(int k=0; k<(i>>1); k++){
            auto u = f[j|k], v = f[j|k|(i>>1)] * root[st * k];
            f[j|k] = u+v, f[j|k|(i>>1)] = 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), r1(n), r2(n);
    for(int i=0; i<_a.size(); i++) a[i] = base(_a[i] >> 10, _a[i] & 1023);
    for(int i=0; i<_b.size(); i++) b[i] = base(_b[i] >> 10, _b[i] & 1023);
    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);
        r1[i] = f1 * (f3 + f4 * base(0, 1));
        r2[i] = f2 * (f3 + f4 * base(0, 1));
    }
    fft(r1, 1); fft(r2, 1);
    vector<ll> ans(n);
    for(int i=0; i<n; i++){
        ll a1 = roundl(r1[i].real());
        ll a2 = roundl(r1[i].imag());
        ll b1 = roundl(r2[i].real());
        ll b2 = roundl(r2[i].imag());
        ans[i] = b2 + ((a2 + b1) << 10) + (a1 << 20);
    }
    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 'void fft(std::vector<std::complex<double> >&, bool)':
tt.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<root.size(); i++) root[i] = base(cos(ang * i), sin(ang * i));
                  ~^~~~~~~~~~~~
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:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<_a.size(); i++) a[i] = base(_a[i] >> 10, _a[i] & 1023);
                  ~^~~~~~~~~~
tt.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<_b.size(); i++) b[i] = base(_b[i] >> 10, _b[i] & 1023);
                  ~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 19 ms 3200 KB Output is correct
2 Incorrect 23 ms 3328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 45820 KB Output is correct
2 Incorrect 330 ms 47536 KB Output isn't correct
3 Halted 0 ms 0 KB -