oj.uz

Submission #222023

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

typedef long long ll;
typedef vector<ll> poly;

ll pw(ll a, ll b, ll mod){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return ret;
}

template<ll mod, ll w>
class NTT{
public:
    void ntt(poly &f, bool inv = 0){
        int n = f.size(), j = 0;
        vector<ll> root(n >> 1);
        for(int i=1; i<n; i++){
            int bit = (n >> 1);
            while(j >= bit){
                j -= bit; bit >>= 1;
            }
            j += bit;
            if(i < j) swap(f[i], f[j]);
        }
        ll ang = pw(w, (mod - 1) / n, mod); if(inv) ang = pw(ang, mod - 2, mod);
        root[0] = 1; for(int i=1; i<(n >> 1); i++) root[i] = root[i-1] * ang % mod;
        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 >> 1); k++){
                    ll u = f[j | k], v = f[j | k | i >> 1] * root[step * k] % mod;
                    f[j | k] = (u + v) % mod;
                    f[j | k | i >> 1] = (u - v) % mod;
                    if(f[j | k | i >> 1] < 0) f[j | k | i >> 1] += mod;
                }
            }
        }
        ll t = pw(n, mod - 2, mod);
        if(inv) for(int i=0; i<n; i++) f[i] = f[i] * t % mod;
    }
    vector<ll> multiply(poly &_a, poly &_b){
        vector<ll> a(all(_a)), b(all(_b));
        int n = 2;
        while(n < a.size() + b.size()) n <<= 1;
        a.resize(n); b.resize(n);
        ntt(a); ntt(b);
        for(int i=0; i<n; i++) a[i] = a[i] * b[i] % mod;
        ntt(a, 1);
        return a;
    }
};

ll ext_gcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(a, b)
  ll g = a; x = 1, y = 0;
  if (b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
  return g;
}
inline ll Mod(ll a, ll b){
    a %= b; if(a < 0) a += b;
    return a;
}
ll inv(ll a, ll m){ //return x when ax mod m = 1, fail -> -1
    ll x, y;
    ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return Mod(x, m);
}

const ll m1 = 2281701377, m2 = 2483027969;
NTT<m1, 3> ntt1;
NTT<m2, 3> ntt2;

ll f(const vector<ll> a){
    vector<ll> rmn(2), lm(2, 1);
    ll ans = 0, M = 1;
    vector<ll> m({m1, m2});
    for(int i=0; i<2; i++){
        ll k = a[i] - rmn[i]; k %= m[i];
        if(k < 0) k += m[i];
        ll x, y;
        ext_gcd(lm[i], m[i], x, y);
        k *= x; k %= m[i];
        if(k < 0) k += m[i];
        ans += k * M % (ll)5e18;
        ans %= (ll)5e18;
        for(int t=i+1; t<2; t++){
            rmn[t] += lm[t] * k;
            rmn[t] %= m[t];
            lm[t] *= m[i];
            lm[t] %= m[t];
        }
        M *= m[i]; M %= (ll)5e18;
    }
    return ans;
}

poly mul(poly &a, poly &b){
    poly a1(a), a2(a);
    poly b1(b), b2(b);
    poly res1 = ntt1.multiply(a1, b1);
    poly res2 = ntt2.multiply(a2, b2);
    poly ret(res1.size());
    for(int i=0; i<res1.size(); i++){
        ret[i] = f({res1[i], res2[i]});
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<ll> a(n+1), b(m+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 'poly mul(poly&, poly&)':
tt.cpp:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<res1.size(); i++){
                  ~^~~~~~~~~~~~
tt.cpp: In instantiation of 'std::vector<long long int> NTT<mod, w>::multiply(poly&, poly&) [with long long int mod = 2281701377; long long int w = 3; poly = std::vector<long long int>]':
tt.cpp:106:37:   required from here
tt.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(n < a.size() + b.size()) n <<= 1;
               ~~^~~~~~~~~~~~~~~~~~~~~
tt.cpp: In instantiation of 'std::vector<long long int> NTT<mod, w>::multiply(poly&, poly&) [with long long int mod = 2483027969; long long int w = 3; poly = std::vector<long long int>]':
tt.cpp:107:37:   required from here
tt.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1980 KB Output is correct
2 Correct 154 ms 6588 KB Output is correct
3 Correct 154 ms 7620 KB Output is correct
4 Correct 305 ms 12344 KB Output is correct
5 Correct 317 ms 13076 KB Output is correct
6 Correct 311 ms 12656 KB Output is correct
7 Correct 314 ms 13392 KB Output is correct
8 Correct 279 ms 13648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 22380 KB Output is correct
2 Correct 1371 ms 43296 KB Output is correct
3 Correct 1406 ms 50308 KB Output is correct
4 Correct 3364 ms 113648 KB Output is correct
5 Correct 3311 ms 106032 KB Output is correct
6 Correct 3350 ms 120436 KB Output is correct
7 Correct 3147 ms 127996 KB Output is correct
8 Correct 3381 ms 126232 KB Output is correct