| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 66499 |
2018-08-11T03:29:26 Z |
IOrtroiii |
Multiply (CEOI17_mul) |
C++14 |
|
70 ms |
9168 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
const double PI = acos(-1);
typedef complex<double> base;
int n;
int rev[N];
void calc_rev(int n,int logn) {
for (int i = 0; i < n; ++i) {
rev[i] = 0;
for (int j = 0; j < logn; ++j) if ((i >> j) & 1) {
rev[i] |= (1 << (logn - 1 - j));
}
}
}
void fft(base a[], int n, bool invert) {
for (int i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int len = 2; len <= n; len <<= 1) {
double alpha = 2 * PI / len * (invert ? -1 : 1);
base wl = base(cos(alpha), sin(alpha));
for (int i = 0; i < n; i += len) {
base w = base(1);
for (int j = 0; j < (len >> 1); ++j) {
base u = a[i + j], v = a[i + j + (len >> 1)] * w;
a[i + j] = u + v;
a[i + j + (len >> 1)] = u - v;
w *= wl;
}
}
}
if (invert) {
for (int i = 0; i < n; ++i) a[i] /= n;
}
}
vector<int> mult(vector<int> a, vector<int> b) {
static base fa[N], fb[N], fc[N];
int na = a.size(), nb = b.size();
int n = 1, logn = 0;
while (n < max(na, nb)) n <<= 1, logn++;
n <<= 1, logn++;
calc_rev(n, logn);
for (int i = 0; i < n; ++i) fa[i] = fb[i] = base(0);
for (int i = 0; i < na; ++i) fa[i] = base(a[i]);
for (int i = 0; i < nb; ++i) fb[i] = base(b[i]);
fft(fa, n, 0), fft(fb, n, 0);
for (int i = 0; i < n; ++i) fc[i] = fa[i] * fb[i];
fft(fc, n, 1);
vector<int> ret;
for (int i = 0; i < na + nb - 1; ++i) ret.push_back((int)(fc[i].real() + 0.5));
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
int n, m; string s, t;
cin >> n >> m >> s >> t;
vector<int> a, b;
for (char c : s) a.push_back(c - '0');
for (char c : t) b.push_back(c - '0');
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
// for (int x : a) cout << x << ' '; cout << '\n';
// for (int x : b) cout << x << ' '; cout << '\n';
vector<int> c = mult(a, b);
c.push_back(0);
// for (int x : c) cout << x << ' '; cout << '\n';
for (int i = 0; i < c.size() - 1; ++i) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
while (c.size() > 1 && !c.back()) c.pop_back();
reverse(c.begin(), c.end());
for (int x : c) cout << x;
}
Compilation message
mul.cpp: In function 'int main()':
mul.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < c.size() - 1; ++i) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
420 KB |
Output is correct |
| 4 |
Correct |
3 ms |
552 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
420 KB |
Output is correct |
| 4 |
Correct |
3 ms |
552 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| 6 |
Correct |
3 ms |
552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
616 KB |
Output is correct |
| 8 |
Correct |
3 ms |
708 KB |
Output is correct |
| 9 |
Correct |
2 ms |
708 KB |
Output is correct |
| 10 |
Correct |
2 ms |
708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
420 KB |
Output is correct |
| 4 |
Correct |
3 ms |
552 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| 6 |
Correct |
3 ms |
552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
616 KB |
Output is correct |
| 8 |
Correct |
3 ms |
708 KB |
Output is correct |
| 9 |
Correct |
2 ms |
708 KB |
Output is correct |
| 10 |
Correct |
2 ms |
708 KB |
Output is correct |
| 11 |
Correct |
9 ms |
1724 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1732 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1732 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1924 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
420 KB |
Output is correct |
| 4 |
Correct |
3 ms |
552 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| 6 |
Correct |
3 ms |
552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
616 KB |
Output is correct |
| 8 |
Correct |
3 ms |
708 KB |
Output is correct |
| 9 |
Correct |
2 ms |
708 KB |
Output is correct |
| 10 |
Correct |
2 ms |
708 KB |
Output is correct |
| 11 |
Correct |
9 ms |
1724 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1732 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1732 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1924 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1924 KB |
Output is correct |
| 16 |
Correct |
31 ms |
5068 KB |
Output is correct |
| 17 |
Correct |
57 ms |
9040 KB |
Output is correct |
| 18 |
Correct |
62 ms |
9040 KB |
Output is correct |
| 19 |
Correct |
70 ms |
9168 KB |
Output is correct |
| 20 |
Correct |
60 ms |
9168 KB |
Output is correct |
