[2019杭电多校第七场][hdu6656]Kejin Player

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6656

题意为从i级花费a元有p的概率升到i+1级，有1-p的概率降到x级(x<i),查询从L级升到R级的花费期望。

菜鸡才知道期望是有可加性的QAQ，即1-5的期望==1-2的期望+2-5的期望。

如果明确这一点就可以比较轻松的推出转移方程.....阿勒？

感觉和我往常见得有点不一样啊QAQ。

按照以往的思路，我会设dp[i]为i到n的期望，则转移方程为$dp[i]=p*dp[i+1]+(1-p)*dp[x[i]]+a[i]$

然后....就没有然后了，只能暴力跑高斯消元了。

可是按照以往的套路来说，不是会有很棒的化简方式使得式子可以直接退出来吗。

所以去巨佬们的博客学习一番后回来搞了搞。

大致的思路是这样的，先设f[i]表示从第i级到第i+1级的期望,dp[i]表示从第1级到第i级的期望，对于f[i] ,有p的概率交钱直接变成i+1，有(1-p)的概率回到x级，那么回到x级后想要升级到i+1，需要dp[i]-dp[x]升回到i级，再+f[i]到i+1级,则转移方程为$f[i]=p*a[i]+(1-p)*(dp[i]-dp[x[i]]+f[i]+a[i])$

涨姿势了QAQ

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn = 5e5 + ;

 const ll mod = 1e9 + ;

 const ll qpow(ll a, ll b) {

     ll ans = ;

     while (b) {

         if (b & )

             ans = a * ans%mod;

         a = a * a%mod;

         b /= ;

     }

     return ans;

 }

 ll r[maxn], s[maxn], x[maxn], a[maxn], dp[maxn];

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         int n, q;

         scanf("%d%d", &n, &q);

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

             scanf("%lld%lld%lld%lld", &r[i], &s[i], &x[i], &a[i]);

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

             ll p = r[i] * qpow(s[i], mod - ) % mod;

             ll pp = qpow(p, mod - ) % mod;

             ll f = (a[i] + ( + mod - p) % mod*(dp[i] + mod - dp[x[i]]) % mod) % mod*pp%mod;

             dp[i + ] = (dp[i] + f) % mod;

         }

         while (q--) {

             int l, r;

             scanf("%d%d", &l, &r);

             printf("%lld\n", (dp[r] - dp[l] + mod) % mod);

         }

     }

 }

巴特西

[2019杭电多校第七场][hdu6656]Kejin Player

最新文章

热门文章