This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
struct bigint : vector<int> {
const static int base = 1e9, wid = log10(base);
bool neg = false;
bigint() {}
bigint(string s) {
if (s == "-0") {
emplace_back(0);
return;
}
if (s[0] == '-') {
neg = true;
s = s.substr(1);
}
for (int i = s.size() - 1, cnt = 0, val = 0, ten = 1; i >= 0; i--) {
cnt++;
val += (s[i] - '0') * ten;
ten *= 10;
if (i == 0 || cnt == wid) {
emplace_back(val);
cnt = val = 0;
ten = 1;
}
}
}
template<typename T>
bigint(const T& val) : bigint(to_string(val)) {}
template<typename T>
bigint& operator = (const T &rhs) {
*this = bigint(rhs);
return *this;
}
template<typename T>
operator T() {
stringstream ss;
ss << *this;
T re;
ss >> re;
return re;
}
int abscmp(const bigint& rhs) const {
if (size() != rhs.size()) {
return size() > rhs.size() ? 1 : -1;
}
for (int i = size() - 1; i >= 0; i--) {
if ((*this)[i] != rhs[i]) {
return (*this)[i] > rhs[i] ? 1 : -1;
}
}
return 0;
}
int cmp(const bigint& rhs) const {
if (neg != rhs.neg) {
return neg == true ? -1 : 1;
}
return neg == true ? -abscmp(rhs) : abscmp(rhs);
}
bool operator < (const bigint& rhs) const {
return cmp(rhs) < 0;
}
bool operator > (const bigint& rhs) const {
return cmp(rhs) > 0;
}
bool operator <= (const bigint& rhs) const {
return cmp(rhs) <= 0;
}
bool operator >= (const bigint& rhs) const {
return cmp(rhs) >= 0;
}
bool operator == (const bigint& rhs) const {
return cmp(rhs) == 0;
}
bool operator != (const bigint& rhs) const {
return cmp(rhs) != 0;
}
bigint& operator += (const bigint& rhs) {
return *this = *this + rhs;
}
bigint& operator ++ () {
return *this = *this + 1;
}
bigint& operator -= (const bigint& rhs) {
return *this = *this - rhs;
}
bigint& operator -- () {
return *this = *this - 1;
}
bigint& operator *= (const bigint& rhs) {
return *this = *this * rhs;
}
bigint& operator /= (const bigint& rhs) {
return *this = *this / rhs;
}
bigint& operator %= (const bigint& rhs) {
return *this = *this % rhs;
}
bigint abs() const {
bigint re = *this;
re.neg = false;
return re;
}
void carry() {
emplace_back(0);
for (int i = 0; i < size(); i++) {
if ((*this)[i] < 0) {
(*this)[i] += base;
(*this)[i + 1]--;
}
if ((*this)[i] >= base) {
(*this)[i] -= base;
(*this)[i + 1]++;
}
}
while (size() && back() == 0) {
pop_back();
}
if (size() == 0) {
neg = false;
emplace_back(0);
}
}
bigint operator -() const {
if (*this == 0) {
return *this;
}
bigint re = *this;
re.neg ^= 1;
return re;
}
friend bigint operator + (bigint lhs, bigint rhs) {
if (lhs.neg == true) {
return -(-lhs + -rhs);
}
if (rhs.neg == true) {
return lhs - -rhs;
}
if (lhs.size() < rhs.size()) {
lhs.resize(rhs.size(), 0);
}
for (int i = 0; i < rhs.size(); i++) {
lhs[i] += rhs[i];
}
lhs.carry();
return lhs;
}
friend bigint operator - (bigint lhs, bigint rhs) {
if (lhs.neg == true) {
return -(-lhs - -rhs);
}
if (rhs.neg == true) {
return lhs + -rhs;
}
if (lhs.abscmp(rhs) < 0) {
return -(rhs - lhs);
}
for (int i = 0; i < rhs.size(); i++) {
lhs[i] -= rhs[i];
}
lhs.carry();
return lhs;
}
friend bigint operator * (bigint lhs, bigint rhs) {
if (lhs == 0 || rhs == 0) {
return 0;
}
bigint re;
re.neg = lhs.neg ^ rhs.neg;
vector<long long> tmp;
auto add = [&](int i, long long val) {
while (i >= tmp.size()) {
tmp.emplace_back(0);
}
tmp[i] += val;
};
for (int i = 0; i < lhs.size(); i++) {
for (int j = 0; j < rhs.size(); j++) {
add(i + j, 1ll * lhs[i] * rhs[j]);
}
for (int j = 0; j < tmp.size(); j++) {
if (tmp[j] >= base) {
add(j + 1, tmp[j] / base);
tmp[j] %= base;
}
}
}
re.resize(tmp.size());
for (int i = 0; i < tmp.size(); i++) {
re[i] = tmp[i];
}
return re;
}
friend bigint operator / (bigint lhs, bigint rhs) {
assert(rhs != 0);
if (lhs == 0) {
return 0;
}
int norm = base / (rhs.back() + 1);
bigint x = lhs.abs() * norm;
bigint y = rhs.abs() * norm;
bigint q, r;
q.resize(x.size());
for (int i = x.size() - 1; i >= 0; i--) {
r = r * base + x[i];
int s1 = r.size() <= y.size() ? 0 : r[y.size()];
int s2 = r.size() < y.size() ? 0 : r[y.size() - 1];
int d = (1ll * base * s1 + s2) / y.back();
r = r - y * d;
while (r.neg == true) {
r += y;
d--;
}
q[i] = d;
}
q.neg = lhs.neg ^ rhs.neg;
q.carry();
return q;
}
friend bigint operator % (bigint lhs, bigint rhs) {
return lhs - (lhs / rhs) * rhs;
}
friend istream& operator >> (istream& ss, bigint& val) {
string s;
ss >> s;
val = s;
return ss;
}
friend ostream& operator << (ostream& ss, const bigint& val) {
if (val.neg == true) {
ss << '-';
}
ss << val.back();
for (int i = (int)val.size() - 2; i >= 0; i--) {
ss << string(wid - to_string(val[i]).size(), '0') << val[i];
}
return ss;
}
};
bigint two[512];
int n, k;
void solve() {
cin >> n >> k;
if (n == 1) {
cout << "1\n";
cout << "A=A\n";
return;
}
int m = __lg(n - 1) + 1;
cout << m << '\n';
two[0] = 1;
FOR (i, 1, 511) two[i] = two[i - 1] * 2;
for (int len = 1, i = 0; len < n; len <<= 1, i++) {
bigint sum = 0;
for (int j = 0; j < n; j += 2 * len) FOR (k, j, j + len - 1) if (k < n) sum += two[k];
cout << "A=" << "((A&" << sum << ")+((A>>" << len << ")&" << sum << "))\n";
}
}
int main() {
Waimai;
solve();
}
Compilation message (stderr)
popcount.cpp: In member function 'void bigint::carry()':
popcount.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < size(); i++) {
| ~~^~~~~~~~
popcount.cpp: In function 'bigint operator+(bigint, bigint)':
popcount.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for (int i = 0; i < rhs.size(); i++) {
| ~~^~~~~~~~~~~~
popcount.cpp: In function 'bigint operator-(bigint, bigint)':
popcount.cpp:176:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for (int i = 0; i < rhs.size(); i++) {
| ~~^~~~~~~~~~~~
popcount.cpp: In lambda function:
popcount.cpp:190:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | while (i >= tmp.size()) {
| ~~^~~~~~~~~~~~~
popcount.cpp: In function 'bigint operator*(bigint, bigint)':
popcount.cpp:195:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int i = 0; i < lhs.size(); i++) {
| ~~^~~~~~~~~~~~
popcount.cpp:196:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for (int j = 0; j < rhs.size(); j++) {
| ~~^~~~~~~~~~~~
popcount.cpp:199:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for (int j = 0; j < tmp.size(); j++) {
| ~~^~~~~~~~~~~~
popcount.cpp:207:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for (int i = 0; i < tmp.size(); i++) {
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |