| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 32093 |
2017-09-25T01:31:11 Z |
h0ngjun7 |
씽크스몰 (kriii3_TT) |
C++14 |
|
3553 ms |
280624 KB |
#include <stdio.h>
#include <complex>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const double PI = 3.1415926535897932384626433832795;
namespace FFT {
typedef complex<double> base;
void FFT(vector <base> &v, bool inv) {
vector<base> w(v.size());
for (int i = 0; i < v.size(); i++) {
int k = i&-i;
if (i == k) {
double ang = 2 * PI * i / v.size();
if (inv) ang *= -1;
w[i] = base(cos(ang), sin(ang));
}
else w[i] = w[i - k] * w[k];
}
for (int i = 1, j = 0; i < v.size(); i++) {
int bit = v.size() >> 1;
for (; j >= bit; bit >>= 1) j -= bit;
j += bit;
if (i < j) swap(v[i], v[j]);
}
for (int i = 2; i <= v.size(); i <<= 1) {
for (int j = 0; j < v.size(); j += i) {
for (int k = 0; k < i / 2; k++) {
base a = v[j + k], b = v[j + k + i / 2] * w[k * (v.size() / i)];
v[j + k] = a + b;
v[j + k + i / 2] = a - b;
}
}
}
if (inv) {
for (int i = 0; i < v.size(); i++) {
v[i] /= v.size();
}
}
}
vector <ll> mul(vector <ll> &v, vector <ll> &w) {
vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
int n = 1;
while (n < max(v.size(), w.size())) n <<= 1;
n <<= 1;
fv.resize(n);
fw.resize(n);
FFT(fv, 0);
FFT(fw, 0);
for (int i = 0; i < n; i++) fv[i] *= fw[i];
FFT(fv, 1);
vector <ll> ret(n);
for (int i = 0; i < n; i++) ret[i] = round(fv[i].real());
return ret;
}
vector <ll> pw(vector <ll> &v) {
vector<base> fv(v.begin(), v.end());
int n = 1;
while (n < v.size()) n <<= 1;
n <<= 1;
fv.resize(n);
FFT(fv, 0);
for (int i = 0; i < n; i++) fv[i] *= fv[i];
FFT(fv, 1);
vector <ll> ret(n);
for (int i = 0; i < n; i++) ret[i] = round(fv[i].real());
return ret;
}
vector <ll> mul(vector <ll> &v, vector <ll> &w, int b) {
int n = 1;
while (n < v.size() || n < w.size()) n <<= 1;
n <<= 1;
vector<base> v1(n), v2(n), v3(n), v4(n), r1(n), r2(n), r3(n);
for (int i = 0; i < v.size(); i++) {
v1[i] = base(v[i] / b, 0);
v2[i] = base(v[i] % b, 0);
}
for (int i = 0; i < w.size(); i++) {
v3[i] = base(w[i] / b, 0);
v4[i] = base(w[i] % b, 0);
}
FFT(v1, 0); FFT(v2, 0); FFT(v3, 0); FFT(v4, 0);
for (int i = 0; i < n; i++) {
r1[i] = v1[i] * v3[i];
r2[i] = v1[i] * v4[i] + v2[i] * v3[i];
r3[i] = v2[i] * v4[i];
}
FFT(r1, 1); FFT(r2, 1); FFT(r3, 1);
vector <ll> ret(n);
for (int i = 0; i < n; i++) {
ret[i] = (ll)round(r1[i].real()) * b * b + (ll)round(r2[i].real()) * b + (ll)round(r3[i].real());
}
return ret;
}
}
int main() {
int N, M; scanf("%d%d", &N, &M);
vector <ll> a, b;
for (int i = 0; i <= N; i++) {
ll x; scanf("%lld", &x);
a.push_back(x);
}
for (int i = 0; i <= M; i++) {
ll x; scanf("%lld", &x);
b.push_back(x);
}
vector <ll> ans = FFT::mul(a, b, (1 << 10));
ll res = 0;
for (int i = 0; i <= N + M; i++) res ^= ans[i];
printf("%lld\n", res);
}
Compilation message
tt.cpp: In function 'void FFT::FFT(std::vector<std::complex<double> >&, bool)':
tt.cpp:15:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
^
tt.cpp:24:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1, j = 0; i < v.size(); i++) {
^
tt.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 2; i <= v.size(); i <<= 1) {
^
tt.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); j += i) {
^
tt.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
^
tt.cpp: In function 'std::vector<long long int> FFT::mul(std::vector<long long int>&, std::vector<long long int>&)':
tt.cpp:48:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (n < max(v.size(), w.size())) n <<= 1;
^
tt.cpp: In function 'std::vector<long long int> FFT::pw(std::vector<long long int>&)':
tt.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (n < v.size()) n <<= 1;
^
tt.cpp: In function 'std::vector<long long int> FFT::mul(std::vector<long long int>&, std::vector<long long int>&, int)':
tt.cpp:75:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (n < v.size() || n < w.size()) n <<= 1;
^
tt.cpp:75:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (n < v.size() || n < w.size()) n <<= 1;
^
tt.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
^
tt.cpp:82:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < w.size(); i++) {
^
tt.cpp: In function 'int main()':
tt.cpp:104:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N, M; scanf("%d%d", &N, &M);
^
tt.cpp:107:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll x; scanf("%lld", &x);
^
tt.cpp:111:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll x; scanf("%lld", &x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1980 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1980 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1980 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2272 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2272 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2272 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
6448 KB |
Output is correct |
| 2 |
Correct |
256 ms |
36016 KB |
Output is correct |
| 3 |
Correct |
276 ms |
36908 KB |
Output is correct |
| 4 |
Correct |
313 ms |
36912 KB |
Output is correct |
| 5 |
Correct |
266 ms |
36912 KB |
Output is correct |
| 6 |
Correct |
306 ms |
36912 KB |
Output is correct |
| 7 |
Correct |
276 ms |
36912 KB |
Output is correct |
| 8 |
Correct |
289 ms |
36912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
696 ms |
71724 KB |
Output is correct |
| 2 |
Correct |
1573 ms |
139312 KB |
Output is correct |
| 3 |
Correct |
1406 ms |
141360 KB |
Output is correct |
| 4 |
Correct |
3503 ms |
280624 KB |
Output is correct |
| 5 |
Correct |
3376 ms |
280624 KB |
Output is correct |
| 6 |
Correct |
3406 ms |
280624 KB |
Output is correct |
| 7 |
Correct |
3453 ms |
280624 KB |
Output is correct |
| 8 |
Correct |
3553 ms |
280624 KB |
Output is correct |
