Submission #222020

#	Time	Username	Problem	Language	Result	Execution time	Memory
222020		jhnah917	씽크스몰 (kriii3_TT)	C++14	0 / 30	296 ms	44396 KiB

tt

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10