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

发布时间:2022-04-30 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了[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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorIThm>
 6 using namespace std;
 7 tyPEdef long long ll;
 8 const int maxn = 5e5 + 10;
 9 const ll mod = 1e9 + 7;
10 const ll qpow(ll a,ll b) {
11     ll ans = 1;
12     while (b) {
13         if (b &amp; 1)
14             ans = a * ans%mod;
15         a = a * a%mod;
16         b /= 2;
17     }
18     return ans;
19 }
20 ll r[maxn],s[maxn],x[maxn],a[maxn],dp[maxn];
21 int main() {
22     int t;
23     scanf("%d",&t);
24     while (t--) {
25         int n,q;
26         scanf("%d%d",&n,&q);
27         for (int i = 1; i <= n; i++)
28             scanf("%lld%lld%lld%lld",&r[i],&s[i],&x[i],&a[i]);
29         for (int i = 1; i <= n; i++) {
30             ll p = r[i] * qpow(s[i],mod - 2) % mod;
31             ll pp = qpow(p,mod - 2) % mod;
32             ll f = (a[i] + (1 + mod - p) % mod*(dp[i] + mod - dp[x[i]]) % mod) % mod*pp%mod;
33             dp[i + 1] = (dp[i] + f) % mod;
34         }
35         while (q--) {
36             int l,r;
37             scanf("%d%d",&l,&r);
38             PRintf("%lld\n",(dp[r] - dp[l] + mod) % mod);
39         }
40     }
41 }

脚本宝典总结

以上是脚本宝典为你收集整理的[2019杭电多校第七场][hdu6656]Kejin Player全部内容,希望文章能够帮你解决[2019杭电多校第七场][hdu6656]Kejin Player所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。