首页 > 试题广场 >

Tree IV

[编程题]Tree IV
  • 热度指数:307 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一棵有n个结点的标准的完全二叉树(即,若父结点编号为x,则它的两个子结点的编号分别为),定义每个结点的价值为xdep_x,即每个点的编号乘以每个点的深度(深度即为从根结点到这一结点最短路径经过的点的个数,定义根结点1的深度为1)。

请你求解这棵树中每个结点的价值和(由于答案可能会很大,请你对998244353取模),即

完全二叉树:若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第 k 层所有的结点都连续集中在最左边。
例如(图为一棵标准的完全二叉树):

示例1

输入

2

输出

5
示例2

输入

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

发表于 2021-08-27 13:16:16 回复(0)
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的吗?难道我记错了?

发表于 2021-01-02 17:58:18 回复(0)