[Hackerearth] StickerMix

 

Problem Link    : StickerMix
Category        : Math, Derangement
Contest         : December Circuits'23

#include "bits/stdc++.h"
using namespace std;
#define endl    '\n'
 
template <const int32_t MOD> struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (modint<MOD> other) const { return value == other.value; }
    inline bool operator != (modint<MOD> other) const { return value != other.value; }
    inline bool operator < (modint<MOD> other) const { return value < other.value; }
    inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
const int mod = 1e9 + 7;
using mint = modint<mod>;
 
const int maxn = 1e6 + 5;
 
mint fact[maxn];
mint derangements[maxn];
 
mint nCr(int n, int r) {
    return fact[n] / (fact[r] * fact[n - r]);
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    fact[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = i * fact[i - 1];
        derangements[i] = i <= 2 ? i - 1 : (i - 1) * (derangements[i - 1] + derangements[i - 2]);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            mint probability = nCr(n, i) * derangements[n - i] / fact[n];
            cout << probability << " ";
        }
        mint probability = mint(1) / fact[n];
        cout << probability << endl;
    }
}

[Hackerearth] EvenOddity

 

Problem Link    : EvenOddity
Category        : Data Structure, Counting, Bits, Centroid Decomposition
Contest         : December Circuits'23  
Tutorial        : Counting Subarrays 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 1e6 + 5;
 
struct Node {
    int v, w;
    Node(int v = 0, int w = 0)
        : v(v), w(w) {}
};
 
int n;
vector<vector<Node>> graph;
vector<int> subtree;
vector<bool> isCentroid;
int curTreeNodes;
 
void calcSubtreeSize(int u, int p) {
    subtree[u] = 1;
    for (Node it : graph[u]) {
        int v = it.v;
        if (v == p or isCentroid[v]) {
            continue;
        }
        calcSubtreeSize(v, u);
        subtree[u] += subtree[v];
    }
}
 
int getCentroid(int u, int p) {
    for (Node it : graph[u]) {
        int v = it.v;
        if (v == p or isCentroid[v]) {
            continue;
        }
        if (subtree[v] > curTreeNodes / 2) {
            return getCentroid(v, u);
        }
    }
    return u;
}
 
int cache[2][2]; // cache[ distance % 2 ][ parity(xorSum) % 2 ]
int curCache[2][2];
int ans;
 
void add(int u, int p, int lvl, int xorSum) {
    int bit = lvl & 1;
    int parity = __builtin_popcount(xorSum) & 1;
    int curAns = cache[bit ^ 1][parity];
    ans += curAns;
    curCache[bit][parity]++;
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p or isCentroid[v]) {
            continue;
        }
        add(v, u, lvl + 1, xorSum ^ w);
    }
}
 
void decompose(int u) {
    calcSubtreeSize(u, 0);
    curTreeNodes = subtree[u];
    int centroid = getCentroid(u, 0);
    isCentroid[centroid] = true;
    memset(cache, 0, sizeof cache);
    cache[0][0] = 1;
    for (Node it : graph[centroid]) {
        int child = it.v;
        if (isCentroid[child]) {
            continue;
        }
        memset(curCache, 0, sizeof curCache);
        add(child, centroid, 1, it.w);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                cache[i][j] += curCache[i][j];
            }
        }
    }
    for (Node it : graph[centroid]) {
        int child = it.v;
        if (isCentroid[child]) {
            continue;
        }
        decompose(child);
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("f2.txt", "r")) {
        freopen("f2.txt", "r", stdin);
        freopen("f2out.txt", "w", stdout);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        cin >> n;
        graph.clear(); graph.resize(n + 1);
        subtree.clear(); subtree.resize(n + 1);
        isCentroid.clear(); isCentroid.resize(n + 1);
        for (int e = 1; e < n; e++) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        }
        ans = 0;
        decompose(1);
        cout << ans * 2 << endl;
    }
}

[Hackerearth] Curious Queries

 

Problem Link    : Curious Queries
Category        : Merge Sort Tree
Contest         : December Circuits'23  

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
using pii = pair<int, int>;
 
const int maxn = 1e5 + 5;
 
struct MergesortTree {
    vector<pii> store;
    MergesortTree() {
        store.clear();
    }
 
    void assignLeaf(int val) {
        store.clear();
        store.push_back({val, val});
    }
    void marge(const MergesortTree &lchild, const MergesortTree &rchild) {
        int i = 0;
        int j = 0;
        store.clear();
        while (i < lchild.store.size() and j < rchild.store.size()) {
            if (lchild.store[i].first < rchild.store[j].first) {
                int sum = lchild.store[i].first + (store.size() ? store.back().second : 0);
                store.emplace_back(lchild.store[i].first, sum);
                i++;
            } else {
                int sum = rchild.store[j].first + (store.size() ? store.back().second : 0);
                store.emplace_back(rchild.store[j].first, sum);
                j++;
            }
        }
        while (i < lchild.store.size()) {
            int sum = lchild.store[i].first + (store.size() ? store.back().second : 0);
            store.emplace_back(lchild.store[i].first, sum);
            i++;
        }
        while (j < rchild.store.size()) {
            int sum = rchild.store[j].first + (store.size() ? store.back().second : 0);
            store.emplace_back(rchild.store[j].first, sum);
            j++;
        }
    }
    int getSum(int limit) {
        int id = upper_bound(store.begin(), store.end(), pii(limit, INT_MAX)) - store.begin();
        if (id == store.size()) {
            return 0;
        }
        int sum = store.back().second - (id - 1 >= 0 ? store[id - 1].second : 0);
        return sum;
    }
} Tree[maxn * 4];
 
int n;
int q;
int arr[maxn];
 
void build(int node, int a, int b) {
    if (a == b) {
        Tree[node].assignLeaf(arr[a]);
        return;
    }
    int lchild = node * 2;
    int rchild = node * 2 + 1;
    int mid = (a + b) / 2;
    build(lchild, a, mid);
    build(rchild, mid + 1, b);
    Tree[node].marge(Tree[lchild], Tree[rchild]);
}
 
int query(int node, int a, int b, int i, int j, int limit) {
    if (a > b or a > j or b < i) {
        return 0;
    }
    if (a >= i and b <= j) {
        return Tree[node].getSum(limit);
    }
    int lchild = node * 2;
    int rchild = node * 2 + 1;
    int mid = (a + b) / 2;
    int p = query(lchild, a, mid, i, j, limit);
    int q = query(rchild, mid + 1, b, i, j, limit);
    return p + q;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("F2.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        build(1, 1, n);
        for (int i = 1; i <= q; i++) {
            int l, r;
            cin >> l >> r;
            l++;
            r++;
            int limit = arr[r];
            int ans = query(1, 1, n, 1, l, limit);
            cout << ans << " \n"[i == q];
        }
    }
}