青蛙跳
Description
有 \(n\) 个荷叶按顺序依次排列开，编号为 \(1\) 到 \(n\)，现在有只青蛙在编号为 \(n\) 的荷叶上。它现在自由愉快的跳跃，如果他在编号为 \(i\) 的荷叶上，它会等概率的跳到编号为 \([1,i]\) 的荷叶上，求它跳到编号为 \(1\) 的荷叶上的期望步数。
Samples
5
3.083333
Limitation
1s, 1024KiB for each test case.
\(50\%\) 的数据，不超过 \(5\times 10^3\)
\(100\%\) 的数据，\(n\) 不超过 \(5\times 10^5\)
tutorial
考虑到从\(i\)跳跃到\(1\)对从\(i+1\)跳跃到\(1\)会产生贡献，定义\(dp[i]\)表示从\(i\)点跳跃到\(1\)的期望步数。
由于从\(i\)点跳跃到任何一个点的概率相等，那么每当我们从\(i\)点跳跃到新点\(j\)时，需要再花费\(dp[j]\)步，期望上才能到达\(1\)（需要注意，到达\(j\)点也是需要花费步数的），我们可以得到：
\[dp[n]=\frac {\sum_{i=1}^n{(dp[i]+1)}}{n} \]两边同时乘以\(n\)，有：
\[n*dp[n]=dp[n]+1+\sum_{i=1}^{n-1}(dp[i]+1) \]整理得到：
\[dp[n]=\frac{1+\sum_{i=1}^{n-1}{(dp[i]+1)}}{n-1} \]同时，初始状态\(dp[1]=0\)，使用概率\(dp\)即可解决问题
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7 ;
double dp[N];
int main() {
int n;
cin >> n;
double sum = 0;
for(int i = 2 ; i <= n ; i++) {
dp[i] = (sum+i)/(double)(i-1);
sum += dp[i];
}
printf("%.6lf",dp[n]);
}
吸血鬼
Description
第 \(0\) 天有个 \(n-1\) （\(n(2\le n\le 10^5)\)）人和 \(1\) 个吸血鬼。每天他们中的两个会相遇，如果是同类，就没有变化。 否则与吸血鬼碰面的人就会有 \(p\) 的概率变成吸血鬼。迟早所有的人，都会变成吸血鬼。计算期望的天数。
Samples
4 0.6
9.167
tutorial
只有选到一个人和一个吸血鬼才有可能发生传染。因此我们先分析发生传染的概率，乘以\(p\)就能得到产生吸血鬼的概率。
假设目前已经有了\(i\)人变成吸血鬼，则发生传染的概率是选到一人一鬼的情况除以能发生的所有情况。假设概率为\(P_i\)，有
\[P_i=\frac{\C_{i}^1*\C_{n-i}^1}{\C_n^2}=\frac{2*i*(n-i)}{n*(n-1)} \]由于发生此事件之后，被传染人数有\(p\)概率增加\(1\)，\(1-p\)的概率传染失败。如果我们希望得到人数增加的期望，则要加上传染失败的概率，我们定义\(dp[i]\)为从\(i\)人增加到\(i+1\)人的期望（”发生传染“是一定会有的，故要加上其期望）：
\[dp[i]=\frac{1}{P_i}+(1-p)*dp[i] \]推导得到：
\[dp[i]=\frac{1}{p*P_i} \]
#include<bits/stdc++.h>
using namespace std;
int main() {
double p,n;
cin >> n >> p;
double pre = 0;
for(double i = 2 ; i <= n ; i++) {
pre = pre+n*(n-1)/(i-1)/(n-i+1)/2.0/p;
}
printf("%.3lf",pre);
}
rating
tutorial
杭电经典题，不写题意了，
我们把上分的过程看成登20次台阶。注意到最后能登到20阶台阶的状态一定是19+20（两个账号）
仔细观察从第\(i\)步走到第\(i+1\)步，我们假设第\(i\)步走到第\(i+1\)步的期望是\(dp[i]\)，如果在第\(i\)步走成功了，则到达\(i\)，如果走失败了，则到达\(i-2\)，需要再走\(dp[i-2]+dp[i-1]+dp[i]\)步。
有表达式：
\[dp[i]=p*1+(1-p)*(1+dp[i-2]+dp[i-1]+dp[i]) \]化简得到：
\[dp[i]=\frac{(1-p)*(dp[i-2]+dp[i-1])+1}p \]#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
double f[N];
int main() {
double p;
while(cin >> p) {
f[0] = 1.0/p;
f[1] = (1+(1-p)*f[0])/p;
double sum = f[0]+f[1];
for(int i = 2 ; i <= 19 ; i++) {
f[i]= (1.0+(1.0-p)*(f[i-2]+f[i-1]))/p;
sum += f[i];
}
sum = sum * 2 - f[19];
printf("%.6lf\n",sum);
}
return 0;
}
k小姐的点赞之谜
Description
K 小姐是一位热爱分享知识的博主，她在自己的博客上发布了 \(n\) 篇文章。初始时，每篇文章的点赞数分别为 \(a_1, a_2, ..., a_n\)。
每过一段时间，就会有一位读者随机给一篇文章点赞，每篇文章被点赞的概率相等。K 小姐很好奇，当第一次出现所有文章点赞数均为偶数时，所有文章的总点赞数的期望是多少呢？
tutorial
注意到，每次点赞都会改变一个数字的奇偶性。因此，我们令\(dp[i]\)表示：目前已经有\(i\)个奇数了，变成\(i-1\)个奇数的期望天数。
由于在有\(n\)个奇数时，下次点赞一定会产生一个偶数，因此\(dp[n]=1\)。
对于\(dp[i]\)，每次点赞都有\(i\)个奇数，\(n-i\)个偶数，因此，会有\(\frac i n\)的概率产生一个偶数，\(\frac{n-i}n\)的概率产生奇数。有：
\[dp[i]=\frac i n *1+\frac{n-i}n*(1+dp[i+1]+dp[i]) \]化简：
\[dp[i]=\frac{(n+(n-i)dp[i+1])}i \]知晓期望之后，设目前有\(cnt\)个奇数，全变成偶数的期望就是\(\sum_{i=0}^{cnt} ans[i]\)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+7;
const ll mod = 1e9+7;
ll a[N] , dp[N];
ll qmi(ll m, ll k) {
ll p = mod;
ll res = 1 % p, t = m;
while (k) {
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
int main() {
int n,sum = 0 , cnt = 0;
cin >> n;
for(int i = 1 ; i <= n ; i++) {
int x;
cin >> x;
if(x%2) cnt++;
sum += x;
}
ll ans = sum;
dp[n] = 1;
for(int i = n-1 ; i >= 1 ; i--) {
dp[i] = (dp[i+1]*(n-i)+n)%mod*qmi(i,mod-2);
dp[i] = (dp[i]%mod+mod)%mod;
}
for(int i = 1 ; i <= cnt ; i++) {
ans += dp[i];
ans %= mod;
}
cout << ans;
}