链接: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;