试题E：爬树的甲壳虫

解析：

涉及知识点：

假设数的结构如下图所示,且攀爬一层的单位时间为1：

1、先考虑从第0层到第1层的期望

则期望为：

令F（x）如下，因为p1<1，故p1的无穷大次方为0

所以

2、再考虑第n-1层到n层的期望

同理，

结论：

3、计算

其中

4、代码实现

细节：注意%p*y与*y%p之间的差别

public class ExaminationF {
    final static Long p = 998244353L;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int high = scanner.nextInt();
        Long res = 0L;
        for(int i=0;i<high;i++){
            Long x = scanner.nextLong();
            Long y = scanner.nextLong();
            //如果写成%p*y就会出错
            res = (res+1)*y%p* MathUtils.quickPow(y-x,p-2,p)%p;
            //res = (res+p)%p;
        }
        System.out.println(res);
    }
}

public static Long quickPow(Long a,Long n,Long p){
        //结果
        Long res = 1L;
        while (n != 0) {
            //判断 n 的二进制的最后一位是否为0
            if((n&1)!=0){
                //当n的二进制最后一位为1时，乘以当前的权重
                res = (res*a)%p;
            }
            //更新n，每次n向右移一位
            n = n >> 1;
            //更新每一位的权重
            a = (a*a)%p;
        }
        return res;
    }

完整代码

import java.util.Scanner;

public class Main {

    public static Long quickPow(Long a,Long n,Long p){
        //结果
        Long res = 1L;
        while (n != 0) {
            //判断 n 的二进制的最后一位是否为0
            if((n&1L)!=0){
                //当n的二进制最后一位为1时，乘以当前的权重
                res = (res*a)%p;
            }
            //更新每一位的权重
            a = (a*a)%p;
            //更新n，每次n向右移一位
            n = n >> 1;
        }
        return res;
    }
    public static void main(String[] args) {

        Long p = 998244353L;
        Scanner scanner = new Scanner(System.in);
        int high = scanner.nextInt();
        Long res = 0L;
        for(int i=0;i<high;i++){
            Long x = scanner.nextLong();
            Long y = scanner.nextLong();

            res = (res+1L)*y%p*quickPow(y-x,p-2L,p)%p;
            res = (res+p)%p;
        }
        System.out.println(res);
    }
}

参考资料

测试OJ