牛客编程巅峰赛S2第1场 - 青铜&白银&黄金 Tree IV 第二题题解

链接：https://ac.nowcoder.com/acm/contest/9004/B
直接上代码

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n long长整型 表示标准完全二叉树的结点个数
     * @return long长整型
     */
        // write code here
          public static long tree4 (long n) {
            // write code here
            long index=1;
            int deep=0;
            final int mod=998244353;
            while(index<=n){
                deep++;
                index=index<<1;  
            }
            long sum=0;
            for(int i=1;i<deep;i++){
                sum=(sum+num(i))%mod;
            }
            long last=(long) Math.pow(2, deep-1);

            //sum=(sum+(last+n)%mod*(n-last+1)*deep/2)%mod;这样算也行,直接等差公式,记得取模,不然数太大
            for(long i=last;i<=n;i++) {
                sum=(sum+i*deep)%mod;
            }
            return sum;
    }
     public static long num(int i) {
         final int mod=998244353;
         long base=(long) Math.pow(2,i-1);
         long sum=(base*2-1+base)*base/2*i%mod;
         return sum;
     }
}

在试了十几次不过之后,终于所有用例通过了,差点爆炸
一.大致思路:
1.求出树的最大深度
2.分别求出从第一层到倒数第二层的全部价值和(深度*编号)[每一层的编号是个等差数列]
3.用循环将这些相加,要取模998244353
4.将最后一层单独算,因为最后一层不一定是满的,但也符合等差数列的规律
5.最终将结果相加

二.说一说为什么我的代码一直过不了全部用例
在我算最后一层sum的时候我是直接

sum+=i*deep%mod;

这里导致取模后的结果加给sum,数据小的时候是没问题的,取模后还是等于原值;但是在数据量大的时候取模就会导致数据出差错了,修改后解决了一直通过不了全部用例的问题

sum=(sum+i*deep)%mod;