x

xv

V1

2022/11/14阅读:12主题:默认主题

爬树的甲壳虫

爬树的甲壳虫

关键字:概率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;


分类:

后端

标签:

C++

作者介绍

x
xv
V1