Editorial for Bedao Grand Contest 15 - Sum^2 Xor
Submitting an official solution before solving the problem yourself is a bannable offence.
1. Lời giải ~O(1)~.
Ta nhận xét:
Mỗi cặp vị trí có thể xét độc lập và đáp án giống nhau, có ~\frac{n \times (n - 1)}{2}~ cặp như vậy.
Với mỗi cặp vị trí, mỗi giá trị xor từ ~0 \rightarrow 2^m - 1~ sẽ xuất hiện ~2^m~ lần, như vậy tổng sẽ là ~\frac{(2^m - 1) \times 2^m}{2} \times 2^m~.
~n - 2~ số không thuộc cặp vị trí đang xét, mỗi số có thể mang ~2^m~ giá trị, vậy số bộ sẽ là ~(2^m)^{n-2}~.
~\rightarrow~ Đáp án là ~\frac{n \times (n - 1)}{2} \times \frac{(2^m - 1) \times 2^m}{2} \times 2^m \times (2^m)^{n-2}~.
2. Lời giải ~O(n)~.
Ta sẽ xét bài toán trên từng bit như sau:
Giả sử có ~c~ bit là ~0~ và ~n-c~ bit là ~1~, thì:
Số cách chọn là ~\binom{n}{c}~.
Tổng giá trị XOR là ~c \times (n-c)~ (~0 \oplus 1 = 1 \oplus 0 = 1~).
Số cách chọn các bit khác là ~2^{n(m-1)}~.
Vậy với mỗi bit thì đáp án là ~S = \sum_{c = 0}^{n} \binom{n}{c} \times c \times (n-c) \times 2^{n(m-1)}~.
Tổng giá trị của ~m~ bit là ~2^m - 1~, nên đáp án của bài toán là ~(2^m - 1) \times S~.
/* Author : DeMen100ns (Vo Khac Trieu) School: University of Science, VNU-HCM */ #include <bits/stdc++.h> #define endl '\n' using namespace std; namespace algebra { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> T bpow(T x, int64_t n) { if(n == 0) { return T(1); } else { auto t = bpow(x, n / 2); t = t * t; return n % 2 ? x * t : t; } } template<int m> struct modular { // https://en.wikipedia.org/wiki/Berlekamp-Rabin_algorithm // solves x^2 = y (mod m) assuming m is prime in O(log m). // returns nullopt if no sol. optional<modular> sqrt() const { static modular y; y = *this; if(r == 0) { return 0; } else if(bpow(y, (m - 1) / 2) != modular(1)) { return nullopt; } else { while(true) { modular z = rng(); if(z * z == *this) { return z; } struct lin { modular a, b; lin(modular a, modular b): a(a), b(b) {} lin(modular a): a(a), b(0) {} lin operator * (const lin& t) { return { a * t.a + b * t.b * y, a * t.b + b * t.a }; } } x(z, 1); // z + x x = bpow(x, (m - 1) / 2); if(x.b != modular(0)) { return x.b.inv(); } } } } int r; constexpr modular(): r(0) {} constexpr modular(int64_t rr): r(rr % m) {if(r < 0) r += m;} modular inv() const {return bpow(*this, m - 2);} modular operator - () const {return r ? m - r : 0;} modular operator * (const modular &t) const {return (int64_t)r * t.r % m;} modular operator / (const modular &t) const {return *this * t.inv();} modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;} modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;} modular operator + (const modular &t) const {return modular(*this) += t;} modular operator - (const modular &t) const {return modular(*this) -= t;} modular operator *= (const modular &t) {return *this = *this * t;} modular operator /= (const modular &t) {return *this = *this / t;} bool operator == (const modular &t) const {return r == t.r;} bool operator != (const modular &t) const {return r != t.r;} explicit operator int() const {return r;} int64_t rem() const {return 2 * r > m ? r - m : r;} }; template<int T> istream& operator >> (istream &in, modular<T> &x) { return in >> x.r; } template<int T> ostream& operator << (ostream &out, modular<T> const& x) { return out << x.r; } }; using namespace algebra; const int mod = 998244353; typedef modular<mod> base; const int N = 1e6 + 5; const long long INF = numeric_limits<long long>::max() / 2; const int MAXA = 1e9; const int B = sqrt(N) + 5; void solve(){ base n, m; cin >> n >> m; base tmp = bpow((base)2, (int)m); cout << (n * (n - 1) / (base)2) * (tmp * (tmp - 1) / (base)2) * tmp * bpow(tmp, (int)n - 2); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int test = 1; test <= t; ++test){ solve(); } }
Comments