b_nk_Tree IV(完全二叉树公式)

定义每个结点的价值为(xdep_x),即每个点的编号乘以每个点的深度,算出有n个结点的完全二叉树的总价值

思路
开始想复杂了啊,直接算出左右结点l、r,然后根据(cfrac{(尾项+首项)*项数}{2})就是总和了啊(今晚的脑子帧不好使)

const int mod=998244353;
typedef long long ll;
class Solution {
public:
    ll tree4(ll n) {
        ll ans=0, l=1, r=1;
       for (ll d=1; l<=n; l<<=1, r=(r<<1)+1, d++) {
            if (r<=n) {
                ans+=((r+l)*(r-l+1)>>1)%mod*d;
            } else {
                ans+=((n+l)*(n-l+1)>>1)%mod*d;
            }
        }
        return ans%mod;
    }
};
原文地址:https://www.cnblogs.com/wdt1/p/13996677.html