Editorial for Bedao Grand Contest 15 - Sum^2 Xor


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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

Please read the guidelines before commenting.


There are no comments at the moment.