【组合数学+二叉树】ABC220 E - Distance on Large Perfect Binary Tree

￡神魔★判官ぃ 2024-03-22 13:08 15阅读 0赞

**妈 的这辈子学不会计数**

**急死我了急死我了急死我了**

[E - Distance on Large Perfect Binary Tree (atcoder.jp)][E - Distance on Large Perfect Binary Tree _atcoder.jp]

题意：

![b71974bb846249299040b2013b35e1b8.png][]

思路：

特殊的地方：

D只有2e6

完全二叉树

树上路径

2^N-1很大很大，因此肯定是组合计数问题

因为2e6的数据，大概率复杂度就是O(d)的

考虑枚举路径所经最高层结点的左右链分配的长度

设左链长度为l，右链为d-l

然后结点位置还不确定

该结点只会存在于前n-max(l,d-l)层的树上，因此有(2^n-max(l,d-l))-1种情况

这些确定了之后，由于往下走是往左还是往右不确定，因此也要计数

具体式子如下：

![1955ce8620d948269158879f20493600.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    
    constexpr int MOD = 998244353;
    
    int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
    template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }
    
    struct Z {
        int x;
        Z(int x = 0) : x(norm(x)) {}
        int val() const { return x; }
        Z operator-() const { return Z(norm(MOD - x)); }
        Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
        Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
        Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
        Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
        Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
        friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
        friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
        friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
        friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
    };
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n;
        cin >> n;
        int d;
        cin >> d;
        Z ans = 0;
        for (int i = 0; i <= d; i++) {
            int dep = n - max(i, d - i);
            if (dep >= 1) {
                ans += (binpow(Z(2), dep) - 1) * binpow(Z(2), max(0, i - 1)) * binpow(Z(2), max(0, d - i - 1));
            }
        }
        ans *= 2;
        cout << ans.val() << "\n";
        return 0;
    }

[E - Distance on Large Perfect Binary Tree _atcoder.jp]: https://atcoder.jp/contests/abc220/tasks/abc220_e
[b71974bb846249299040b2013b35e1b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/87b50ac8886c4463ba15582ae59b36bd.png
[1955ce8620d948269158879f20493600.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/fded2290840a43c1b830107245250288.png