爬树的甲壳虫

爬树的甲壳虫

关键字：概率DP；数论（递推推导，费马定理）；快速幂；

问题描述

问题分析

概率DP

递推公式：

• ① 有 的概率会滑落回位置 ，这样之后从位置 开始到达树顶端的平均时间即 ；
• ② 有 的概率停留在位置i + 1，此时状态变为了从位置 到树顶端的平均时间

递推公式化简：

问题转换

给定 的计算式， ，求 , 为所取的模，题目给定的M为质数。

子问题

根据费马小定理：如果p是一个质数，而整数a不是p的倍数，则有 。

除法逆元化简公式：

快速幂（将计算幂值的时间复杂度从O(n)降低到O（nlogn））

快速幂了解：https://blog.csdn.net/qq_19782019/article/details/85621386

//计算base的power次方
long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power % 2 == 1) {
            result = result * base % 1000;
        }
        power = power / 2;
        base = (base * base) % 1000;
    }
    return result;
}

性能优化

long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % 1000;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % 1000;
    }
    return result;
}

代码实现

#include<bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int maxn = 1e5 + 5;
typedef long long LL;
int x[maxn], y[maxn];

// 快速幂 a^n % P 
LL fpow(LL a, int n, int P){
 LL res = 1;
 while (n){
  if(n&1)
   res = res * a % P;
  a = (a * a) % P;
  n >>= 1;
 }
 return res;
}

int main(){
 int n;
 scanf("%d", &n);
 for (int i=1; i<=n; ++i){ 
  scanf("%d%d", &x[i], &y[i]);
 }
 // 计算s(i)和ans = a_0，pre = s(i-1)
 int ans = 0, pre = 1;
 for (int i=1; i<=n; ++i){
  pre = 1LL * pre * y[n-i+1] % MOD 
  * fpow(y[n-i+1]-x[n-i+1], MOD-2, MOD) % MOD;  // y >= x
  ans = (1LL * ans + pre) % MOD;
 }
 printf("%d\n", ans);
 return 0;
}