期望dp与乘法逆元

解题思路:简单的期望dp

注意事项:乘法一定要防止long long越界

参考代码:

#include<bits/stdc++.h>//这道题自己曾经不会期望dp,不会逆元，所以考场做不出来。

//现在自己靠自己写了出来，很好，证明自己进步了。

using namespace std;

typedef long long ll;

#define maxn 100010

ll p=998244353;

ll n,x[maxn],y[maxn],dp[maxn];

ll qpow(ll di,ll zhi,ll mod){

    ll ans=1,base=di;

    while(zhi){

        if(zhi&1)ans*=base;

        base*=base;

        zhi>>=1;//核心代码就这三行

        ans%=mod;

        base%=mod;

    }

    return ans;

}

int main(){

    scanf("%lld",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld%lld",&x[i],&y[i]);

    }

    for(int i=1;i<=n;i++){

        dp[i]=(dp[i-1]+1)*(y[i]%p);

        dp[i]%=p;

        dp[i]*=qpow(y[i]-x[i],p-2,p);//(y[i]-x[i])模p的逆元是(y[i]-x[i])^(p-2)modp

        dp[i]%=p;//这样就百分百不会越ll的界

    }

    printf("%lld",dp[n]);

    system("pause");

    return 0;

}