# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
556471 |
2022-05-03T08:25:59 Z |
cloudholic |
씽크스몰 (kriii3_TT) |
C++17 |
|
2569 ms |
222412 KB |
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define int64 long long
typedef complex<double> base;
void fft(vector <base>& a, const bool invert)
{
const int n = sz(a);
for (int i = 1, j = 0; i < n; i++)
{
int bit = n >> 1;
for (; j >= bit; bit >>= 1)
j -= bit;
j += bit;
if (i < j)
swap(a[i], a[j]);
}
vector<base> root(n / 2);
const double angle = 2 * acos(-1) / n * (invert ? -1 : 1);
for (int i = 0; i < n / 2; i++)
root[i] = base(cos(angle * i), sin(angle * i));
for (int len = 2; len <= n; len <<= 1)
{
const int step = n / len;
for (int i = 0; i < n; i += len)
{
for (int j = 0; j < len / 2; j++)
{
base u = a[i + j];
base v = a[i + j + len / 2] * root[step * j];
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
}
}
}
if (invert)
for (int i = 0; i < n; i++)
a[i] /= n;
}
void multiply(const vector<int>& a, const vector<int>& b, vector<int64>& res)
{
constexpr int cut = 1e3;
vector<base> lower_a, upper_a;
vector<base> lower_b, upper_b;
int n = 1;
while (n < sz(a) + sz(b) - 1)
n <<= 1;
lower_a.resize(n);
upper_a.resize(n);
lower_b.resize(n);
upper_b.resize(n);
for (int i = 0; i < sz(a); i++)
{
lower_a[i] = a[i] % cut;
upper_a[i] = a[i] / cut;
}
for (int i = 0; i < sz(b); i++)
{
lower_b[i] = b[i] % cut;
upper_b[i] = b[i] / cut;
}
fft(lower_a, false);
fft(upper_a, false);
fft(lower_b, false);
fft(upper_b, false);
vector<base> lower_a2(all(lower_a));
vector<base> upper_a2(all(upper_a));
for (int i = 0; i < n; i++)
{
lower_a[i] *= lower_b[i];
lower_a2[i] *= upper_b[i];
upper_a[i] *= lower_b[i];
upper_a2[i] *= upper_b[i];
}
fft(lower_a, true);
fft(lower_a2, true);
fft(upper_a, true);
fft(upper_a2, true);
res.resize(n);
for (int i = 0; i < n; i++)
{
const int64 res_ll = static_cast<int64>(lower_a[i].real() + (lower_a[i].real() > 0 ? 0.5 : -0.5));
const int64 res_lu = static_cast<int64>(lower_a2[i].real() + (lower_a2[i].real() > 0 ? 0.5 : -0.5));
const int64 res_ul = static_cast<int64>(upper_a[i].real() + (upper_a[i].real() > 0 ? 0.5 : -0.5));
const int64 res_uu = static_cast<int64>(upper_a2[i].real() + (upper_a2[i].real() > 0 ? 0.5 : -0.5));
res[i] = res_uu * cut * cut + (res_lu + res_ul) * cut + res_ll;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> f, g;
vector<int64> res;
f.resize(n + 1);
g.resize(m + 1);
for (int i = 0; i <= n; i++)
cin >> f[i];
for (int i = 0; i <= m; i++)
cin >> g[i];
multiply(f, g, res);
int64 result = 0;
for (const auto& i : res)
result ^= i;
cout << result << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
3664 KB |
Output is correct |
2 |
Correct |
89 ms |
14188 KB |
Output is correct |
3 |
Correct |
75 ms |
14260 KB |
Output is correct |
4 |
Correct |
160 ms |
27824 KB |
Output is correct |
5 |
Correct |
129 ms |
27992 KB |
Output is correct |
6 |
Correct |
158 ms |
27844 KB |
Output is correct |
7 |
Correct |
129 ms |
28016 KB |
Output is correct |
8 |
Correct |
135 ms |
28000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
54908 KB |
Output is correct |
2 |
Correct |
1039 ms |
110164 KB |
Output is correct |
3 |
Correct |
1044 ms |
110416 KB |
Output is correct |
4 |
Correct |
2437 ms |
221072 KB |
Output is correct |
5 |
Correct |
2307 ms |
220416 KB |
Output is correct |
6 |
Correct |
2569 ms |
221800 KB |
Output is correct |
7 |
Correct |
2508 ms |
222412 KB |
Output is correct |
8 |
Correct |
2546 ms |
222376 KB |
Output is correct |