【扬中集训Day6T1】 白日梦
【题目描述】
白日梦
(daydream.c/cpp/pas)
时间限制: 1 s 空间限制: 256 MB
题目描述
SR需要相当大的睡眠量
某日,他做了一个奇怪的梦,他梦见自己成为了怪物猎人,为了狩猎,他要去一个岛上住N+1天(编号为0到N)。这个岛位于太平洋中心,每天要么是晴天,要么刮台风。
他到达岛的第0天是晴天。然后对于第i天,假如是晴天,那么有P(0<p<=1)的概率会变天,使得接下来连续M天都刮台风,然后第i+M+1天必然会转晴。
天气对SR的狩猎造成了很大的影响,如果第i天是晴天,那么SR能狩猎到A只猎物;如果刮台风,SR只能狩猎到B只猎物,还有D(0<D<=1)的概率会失败,在失败的情况下,只能狩猎到C只猎物
SR突然幻梦初醒,他想知道编号1到N天的狩猎到的猎物数量和的期望值
设答案为(x与y互素),请你输出x*除以998244353的余数。这里指y的乘法逆元,它是1到998244353-1中的某一个整数,满足*y-1能被998244353整除(题目保证这个数存在)。
输入
一行7个整数N,M,P,D,A,B,C,如题目所描述(其中给出的P,D是模998244353意义下的值)
输出
一个整数,为答案。
样例输入
样例1
3 1 499122177 499122177 1 2 3
样例2
233 23 372752072 54252411 10 20 22
样例输出
样例1
311951365
样例2
651727164
数据规模
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
【题目链接】
http://oj.jzxx.net/problem.php?id=3110
【算法】
概率DP
很显然,每一天对答案的贡献是独立的。设f[i]表示第i天是晴天的概率,考虑第i-1天的天气,如果是晴天,那么f[i-1]*(1- P) 会 转移到f[i]。如果是台风天,表示i-1是连续台风天的第m天,那么第i-m-1天必然是上一个晴天,所以f[i-m-1]*P转移到f[i]。
求出f数组后,就可以直接统计答案输出了。
时间复杂度O(N)
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define MAXN 1000000 typedef long long LL; LL i,N,M,P,D,A,B,C,ans,R;
LL dp[MAXN+]; template <typename T> void read(T &x) {
int f=; char c = getchar(); x=;
for (; !isdigit(c); c = getchar()) { if (c=='-') f=-; }
for (; isdigit(c); c = getchar()) x=x*+c-'';
x*=f;
} template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
} template <typename T> inline void writeln(T x) {
write(x);
puts("");
} int main() { read(N); read(M); read(P); read(D); read(A); read(B); read(C); R = ((LL)B * ( - D) + (LL)C * D) % MOD;
if (R < ) R += MOD;
dp[] = ;
for (i = ; i <= M; i++) dp[i] = (LL)dp[i-] * ( - P) % MOD;
for (i = M + ; i <= N; i++) dp[i] = ((LL)dp[i-] * ( - P) + (LL)dp[i-M-] * P) % MOD;
for (i = ; i <= N; i++) {
if (dp[i] < ) dp[i] += MOD;
ans = (ans + (LL)dp[i] * A + (LL)( - dp[i]) * R) % MOD;
}
if (ans < ) ans += MOD; writeln(ans); return ; }
最新文章
- 为何Redis要比Memcached好用(转)
- a different object with the same identifier value was already associated with the session:错误;
- JS判断设备的类型
- install ios开发环境
- html块级元素和内联元素小结
- DataTable反向模糊匹配查找语法
- linux驱动系列之s3c2440内存布局
- bzoj 1264 [AHOI2006]基因匹配Match(DP+树状数组)
- C# 导入导出excel文件案例
- shiro基础学习(三)&mdash;shiro授权
- 转:Spring历史版本变迁和如今的生态帝国
- Windows无法自动将IP协议堆栈绑定到网络适配器 的解决办法
- CSS 选择器权重计算规则
- Java课程作业之动手动脑(五)
- eclipse导入spring框架
- POJ 2975 Nim(博弈)题解
- Css 特性之 transition和transform
- 《完全版线段树》——notonlysuccess
- 创建ROS工程結構
- JTS(Geometry)(转)