中石油6028 白日梦（dp）
6028: 白日梦
时间限制: 1 Sec 内存限制: 128 MB提交: 38 解决: 20
[ 提交][ 状态][ 讨论版][命题人: admin]
题目描述
SR需要相当大的睡眠量某日，他做了一个奇怪的梦，他梦见自己成为了怪物猎人，为了狩猎，他要去一个岛上住N+1天（编号为0到N）。这个岛位于太平洋中心，每天要么是晴天，要么刮台风。
他到达岛的第0天是晴天。然后对于第i天，假如是晴天，那么有P(0
天气对SR的狩猎造成了很大的影响，如果第i天是晴天，那么SR能狩猎到A只猎物；如果刮台风，SR只能狩猎到B只猎物，还有D(0
SR突然幻梦初醒，他想知道编号1到N天的狩猎到的猎物数量和的期望值
设答案为x/y（x与y互素），请你输出x*y^(-1)除以998244353的余数。这里y^(-1)指y的乘法逆元，它是1到998244353-1中的某一个整数，满足y^(-1)*y-1能被998244353整除（题目保证这个数存在）。
输入
一行7个整数N,M,P,D,A,B,C，如题目所描述（其中给出的P，D是模998244353意义下的值）输出
一个整数，为答案。样例输入
3 1 499122177 499122177 1 2 3
样例输出
311951365
提示
30%的数据：N≤20
50%的数据：N≤2,000
100%的数据：1≤M≤N≤1,000,000 1≤A,B,C≤1,000 1≤P,D＜998244353
提示
样例一输出的值对应的实数是4.6875
来源
2018江苏冬令营5
【分析】
设dp[i]表示第i天为晴天的概率，考虑第i-1天，晴天时，对dp[i]的贡献值为 dp[i-1](1-p)，阴天时，则为第m个阴天，即在i-m-1天发生了变天，对dp[i]贡献值 dp[i-m-1]*p
【代码】
#include
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int mod=998244353;
inline ll inv(ll b){return b==1?1:(mod-mod/b)*inv(mod%b)%mod;}
ll dp[N],n,m,p,d,a,b,c,sum[N];
int main()
{cin>>n>>m>>p>>d>>a>>b>>c;dp[0]=1;ll ans=0;for(int i=1;i<=n;i++){dp[i]=dp[i-1]*(1-p+mod)%mod;if(i-m-1>=0)dp[i]+=dp[i-m-1]*p%mod;dp[i]%=mod;ans+=dp[i] * a%mod;ans+=(1-d+mod)%mod * (1-dp[i]+mod)%mod *b%mod;ans+=d * (1-dp[i]+mod)%mod * c%mod;}cout<<(ans+mod)%mod< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！