请你求解这棵树中每个结点的价值和(由于答案可能会很大,请你对998244353取模),即。
完全二叉树:若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第 k 层所有的结点都连续集中在最左边。
例如(图为一棵标准的完全二叉树):
2
5
5
38
其计算公式为:1 * 1 + (2 + 3) * 2 + (4 + 5) * 3 = 38 (此式乘号前面为结点编号的和,后面为这些节点对应的深度)
数据满足:
import bisect class Solution: def tree4(self , n ): # write code here # 获取最大层数 two = [1] for i in range(30): two.append(two[-1] * 2) pre = [0] for i in range(len(two)): pre.append(pre[-1] + two[i]) pos = bisect.bisect_right(pre,n) height = pos - 1 left = n - pre[pos - 1] mod = 998244353 cnt = 1 cur = 1 ans = 0 while cnt <= height: ans += cnt * ((cur + cur + two[cnt - 1] - 1) * two[cnt - 1] // 2) % mod cur += two[cnt - 1] cnt += 1 if left: ans += pos * ((two[height] + two[height] + left - 1) * left // 2) % mod return ans % mod
M = 998244353 class Solution: def tree4(self, n ): # write code here depth = 0 curDepthMaxNode = 2 ** depth tot = 0 curID = 1 while n >= curDepthMaxNode: depthSum = ((curID % M + curID + curDepthMaxNode - 1) % M * (curDepthMaxNode / float(2) % M)) % M tot += depthSum * (depth + 1) curID += curDepthMaxNode tot %= M depth += 1 n -= curDepthMaxNode curDepthMaxNode = 2 ** depth depthSum = ((curID + curID + n - 1) % M * (n / float(2) % M)) % M tot += depthSum * (depth + 1) tot %= M return tot
吐了,感觉应该是overflow了,因为我随便加几个 mod 就能多过几个test case。 然而python不是应该不会overflow的吗?难道我记错了?