S2赛季第一场A-Tree IV题解

///最多1e9个节点，32层的完全二叉树节点总数为： =4294967296
n个节点的完全二叉树 深度d = log2(n+1)向上取整。（d一定小于32）。
我的做法是预处理每一层的和,sum[i]表示第i层的和。（求和用到了等差数列求和公式）

有两种情况：

一、对于深度为d的完全二叉树是满二叉树时，ret就是sum[1]到sum[d]求和。
比如，n = 7: 树是3层的满二叉树。那么结果就是这3层的和。

二、对于深度为d的完全二叉树不是满二叉树时，对应的深度为d-1的二叉树肯定是满二叉树，处理方法和第一种情况一样。d层剩余节点的标号可以容易推知是 ans[d-1]到n，独立用一次等差数列求和即可得到答案。 即：ret += (int128_t)(ans[d-1]+n)(n-ans[d-1]+1)/2d%998244353;(这里计算的过程中超出了long long的范围了 牛客OJ后台是Linux系统可以用int128)。

（ans[i]表示 完全二叉树第i+1层 最左边的节点编号。上面说的sum[i]求和就是根据ans[i]算出来的，等差数列首项ans[i],末项是ans[i]*2-1,项数是ans[i]-1。）

附上我比赛结束后7分钟才过的代码（本菜如有不对之处，望大佬指正）

long long tree4(long long n) {
    long long sum[100] = {0};
    long long ans[100] = {0};
    long long q = 1;
    for(int i = 0;i < 32;i++) {
        ans [i] = q<<i;
        ans[i] %= 998244353;
    }
    for(int i = 0;i < 31;i++) {
        sum[i+1] = ((ans[i]+(ans[i]*2-1))*ans[i])/2;
        sum[i+1] %= 998244353;
    }
    long long ret = 0;
    int d = ceil(log2(n+1));
    if(n >= ans[d-1]&&n < ans[d-1]*2-1) {
        for(int i = 1;i < d;i++) {
            ret += sum[i]*i;
            ret %= 998244353;
        }
        ret += (__int128_t)(ans[d-1]+n)*(n-ans[d-1]+1)/2*d%998244353;
        ret %= 998244353;
    }
    else {
        for(int i = 1;i <= d;i++) {
            ret += sum[i]*i;
            ret %= 998244353;
        }
    }
    return ret%998244353;
}