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; }