【扬中集训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+10];

template <typename T> void read(T &x) {
        int f=1; char c = getchar(); x=0;
        for (; !isdigit(c); c = getchar()) { if (c=='-') f=-1; }
        for (; isdigit(c); c = getchar()) x=x*10+c-'0';
        x*=f;
}

template <typename T> inline void write(T x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) write(x/10);
    putchar(x%10+'0');    
}

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 * (1 - D) + (LL)C * D) % MOD;
        if (R < 0) R += MOD;
        dp[0] = 1;
        for (i = 1; i <= M; i++) dp[i] = (LL)dp[i-1] * (1 - P) % MOD;
        for (i = M + 1; i <= N; i++) dp[i] = ((LL)dp[i-1] * (1 - P) + (LL)dp[i-M-1] * P) % MOD;
        for (i = 1; i <= N; i++) {
                if (dp[i] < 0) dp[i] += MOD;
                ans = (ans + (LL)dp[i] * A + (LL)(1 - dp[i]) * R) % MOD;
        }
        if (ans < 0) ans += MOD;
        
        writeln(ans);
        
        return 0;
    
}

【扬中集训Day6T1】 白日梦

【扬中集训Day6T1】白日梦