Знову AND на дереві#13124

Знову AND на дереві (Розбір)

Розв'язок

Від кореня до будь-якої вершини результат побітового AND може лише втрачати одиничні біти. Для всіх некореневих вершин кількість таких бітів має бути однаковою. Позначимо цю кількість через . Якщо n>1, то 1\le k\le m: кожен сусід кореня має додатне значення, а AND на шляху до нього дорівнює саме цьому значенню.

Нехай степінь кореня дорівнює . Оскільки кореню присвоєно 2^m-1, кожен із його сусідів повинен мати рівно одиничних бітів. Для кожного сусіда є \binom{m}{k} незалежних варіантів, тому для всіх сусідів — \binom{m}{k}^{d}.

Розглянемо решту n-1-d вершин. На шляху до батька вже залишилося рівно одиничних бітів. Щоб їхня кількість не зменшилася, число в поточній вершині повинно містити одиниці на цих позиціях. Решта m-k бітів довільні, отже, для кожної такої вершини є 2^{m-k} варіантів. Усі ці вибори незалежні.

Таким чином, для фіксованого кількість розстановок дорівнює

\binom{m}{k}^{d}\cdot 2^{(m-k)(n-1-d)}.

Підсумувавши за всіма , отримаємо

\boxed{F(d)=\sum_{k=1}^{m}\binom{m}{k}^{d}\cdot 2^{(m-k)(n-1-d)}} \pmod{998244353}.

Якщо n=1, відповідь для єдиного кореня дорівнює .

Важливо, що залежить лише від степеня кореня, а не від форми дерева. Тому для вершин з однаковими степенями відповідь обчислюємо тільки один раз.

Оптимізація

Біноміальні коефіцієнти обчислюємо за після підготовки факторіалів та обернених факторіалів:

\binom{m}{k}=m!\,(k!)^{-1}\,((m-k)!)^{-1} \pmod{998244353}.

Для всіх обернених факторіалів достатньо одного піднесення до степеня: спочатку знаходимо (MAXN-1)!^{-1}, а потім рухаємося назад за формулою

((i-1)!)^{-1}=i\,(i!)^{-1}\pmod{998244353}.

Для кожного степеня перебираємо від до . Позначимо q=2^{n-1-d}. Тоді

2^{(m-k)(n-1-d)}=q^{m-k}.

Цей множник можна підтримувати змінною : початково p=1, а після кожної ітерації p\leftarrow p\cdot q.

Покажемо, що різних степенів лише O(\sqrt n). Для n\ge2 усі степені додатні. Якщо різних степенів , їхня сума не менша за 1+2+\cdots+s=s(s+1)/2. З іншого боку, сума степенів усіх вершин дерева дорівнює 2(n-1). Тому

\frac{s(s+1)}{2}\le2(n-1), \qquad s=O(\sqrt n).

Отже, замість значень формули достатньо обчислити її для O(\sqrt n) різних степенів. Обчислені відповіді зберігаємо у масиві за степенем вершини.

Складність

Один виклик обчислення перебирає значень і виконує швидке піднесення до степеня на кожній ітерації, тобто займає O(m\log(d+1)) часу. Разом для одного набору даних маємо O(n+m\sqrt n\log n) часу та додаткової пам'яті.

Попередня підготовка факторіалів, обернених факторіалів і степенів двійки виконується один раз за O(MAXN+\log MOD) часу та O(MAXN) пам'яті.

Реалізація C++17

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int maxn = 1e5 + 10;

int fact[maxn], inv_fact[maxn], pw2[maxn];

int binpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

void precalc() {
    fact[0] = pw2[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
        pw2[i] = 2LL * pw2[i - 1] % mod;
    }

    inv_fact[maxn - 1] = binpow(fact[maxn - 1], mod - 2);
    for (int i = maxn - 1; i >= 1; i--)
        inv_fact[i - 1] = 1LL * inv_fact[i] * i % mod;
}

int C(int n, int k) {
    int res = 1LL * fact[n] * inv_fact[k] % mod;
    return 1LL * res * inv_fact[n - k] % mod;
}

int calc(int n, int m, int d) {
    if (n == 1) return 1;

    int ans = 0, p = 1;
    int q = pw2[n - 1 - d];

    for (int k = m; k >= 1; k--) {
        int cur = 1LL * binpow(C(m, k), d) * p % mod;
        ans = (ans + cur) % mod;
        p = 1LL * p * q % mod;
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> deg(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        deg[u]++;
        deg[v]++;
    }

    vector<int> seen(n, -1);
    for (int i = 0; i < n; i++) {
        int d = deg[i];
        if (seen[d] == -1) seen[d] = calc(n, m, d);
        cout << seen[d] << " \n"[i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precalc();

    int t;
    cin >> t;
    while (t--) solve();
}