期望Dp
自己的期望还是太弱了，牢记期望=概率$\times$代价。
Solution
首先我们推一下式子，设$f_i$表示达到第$i$天依然开心的期望。
带入定义式，显然：
$$
f_i=\sum(f_{i-1}+1) \frac{p_i}{100}+2\times(f_{i-1}+1)\frac{p_i}{100}(1-\frac{p_i}{100})+3\times(f_{i-1}+1)\frac{p_i}{100}(1-\frac{p_i}{100})^2\dots
$$
简单化简一下：
$$
f_i=\frac{100}{p_i}\times(f_{i-1}+1)
$$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
if(res < 0) putchar('-'), res = -res;
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 2e5 + 5, mod = 998244353;
int n, m;
int p[N], f[N];
inline int qpow(int x, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
k >>= 1;
}
return res;
}
int main()
{
read(n);
for(int i = 1;i <= n;i ++) read(p[i]), p[i] = qpow(p[i], mod - 2);
for(int i = 1;i <= n;i ++) f[i] = 1ll * (f[i - 1] + 1) * p[i] % mod * 100 % mod;
write(f[n]);
return 0;
}
|