| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 222019 |
2020-04-11T21:14:21 Z |
jhnah917 |
씽크스몰 (kriii3_TT) |
C++14 |
|
372 ms |
25240 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);
}
/*
256183405 757402647
512366810 516560941
*/
const ll m1 = 2113929217, m2 = 998244353;
NTT<m1, 5> ntt1;
NTT<m2, 3> ntt2;
ll f(ll a, ll b){
ll s, t;
ll g = ext_gcd(m1, m2, s, t);
s = s * b % m2;
t = t * a % m1;
return (s * (m1 / g) + t * (m2 / g)) % (m1 * m2);
}
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(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 'poly mul(poly&, poly&)':
tt.cpp:98: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 = 2113929217; long long int w = 5; poly = std::vector<long long int>]':
tt.cpp:95: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 = 998244353; long long int w = 3; poly = std::vector<long long int>]':
tt.cpp:96:37: required from here
tt.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
| # |
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 |
4 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1852 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
1852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
372 ms |
25240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
