概率与统计

多无趣的实验啊，还是来写题罢

搞笑世界杯

题目背景

很久很久以后，一次世界杯。

题目描述

随着世界杯小组赛的结束，法国，阿根廷等世界强队都纷纷被淘汰，让人心痛不已。于是有人组织了一场搞笑世界杯，将这些被淘汰的强队重新组织起来和世界杯一同比赛。你和你的朋友欣然去购买球票。不过搞笑世界杯的球票出售方式也很特别，它们只准备了两种球票。

A 类票——免费球票
B 类票——双倍价钱球票。

购买时由工作人员通过掷硬币决定，投到正面的买 A 类票，反面的买 B 类票。主办方总是准备了同样多的 A 类票和 B 类票。你和你的朋友十分幸运的排到了某场精彩比赛的最后两个位置。

这时工作人员开始通过硬币售票。不过更为幸运的是当工作人员到你们面前时他发现已无需再掷硬币了，因为剩下的这两张票全是免费票。

你和你的朋友在欣喜之余，想计算一下排在队尾的两个人同时拿到一种票的概率是多少(包括同时拿 A 类票或 B 类票) 假设工作人员准备了 $2n$ 张球票，其中 $n$ 张 A 类票，$n$ 张 B 类票，并且排在队伍中的人每人必须且只能买一张球票(不管掷到的是该买 A 还是该买 B)。

输入格式

输入只有一行一个整数，表示 $2n$。

输出格式

输出只包含一行一个浮点数，为拿到同一种票的概率，精确到小数点后 4 位。

样例 #1

样例输入 #1

样例输出 #1

0.9500

提示

数据规模与约定

对全部的测试点，保证 $1 \leq n \leq 1250$。

题解：

很容易想到用dp

用f(i,j)表示卖出i张A，j张B后两人买到票相同的概率

则容易得到

1	f[i][k]=f[i-1][k]0.5+f[i][k-1]0.5;

最后只需要输出f[n] [n]即可

#include<iostream>
using namespace std;
const int M=1500;
int n;
double f[M][M];
int main()
{
cin>>n;
        n>>=1;
    for (int i=2;i<=n;i++)
        f[i][0]=1,f[0][i]=1; 
    for (int i=1;i<=n;i++)
        for (int k=1;k<=n;k++)
        {
            f[i][k]=f[i-1][k]*0.5+f[i][k-1]*0.5;
        }
    printf("%.4lf",f[n][n]);
}

OSU!

题目背景

原《产品排序》参见P2577

题目描述

osu 是一款群众喜闻乐见的休闲软件。

我们可以把 osu 的规则简化与改编成以下的样子:

一共有 $n$ 次操作，每次操作只有成功与失败之分，成功对应 $1$，失败对应 $0$，$n$ 次操作对应为 $1$ 个长度为 $n$ 的 01 串。在这个串中连续的 $X$ 个 $1$ 可以贡献 $X^3$ 的分数，这 $x$ 个 $1$ 不能被其他连续的 $1$ 所包含（也就是极长的一串 $1$，具体见样例解释）

现在给出 $n$，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 $1$ 位小数。

输入格式

第一行有一个正整数 $n$，表示操作个数。接下去 $n$ 行每行有一个 $[0,1]$ 之间的实数，表示每个操作的成功率。

输出格式

只有一个实数，表示答案。答案四舍五入后保留 $1$ 位小数。

样例 #1

样例输入 #1

样例输出 #1

6.0

提示

【样例说明】

$000$ 分数为 $0$，$001$ 分数为 $1$，$010$ 分数为 $1$，$100$ 分数为 $1$，$101$ 分数为 $2$，$110$ 分数为 $8$，$011$ 分数为 $8$，$111$ 分数为 $27$，总和为 $48$，期望为 $\dfrac{48}8 = 6.0$。

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int  i=a;i>=ni--)
using ll=long long;
using namespace std;
int n;
const int N=1e5+100;
double p[N];
double x1[N];
double x2[N];
double ans[N];
int main()
{
cin>>n;
rep(i,1,n)
{
    cin>>p[i];
}
rep(i,1,n)
{
    x1[i]=(x1[i-1]+1)*p[i];
    x2[i]=(x2[i-1]+2*x1[i-1]+1)*p[i];
    ans[i]=ans[i-1]+(3*(x1[i-1]+x2[i-1])+1)*p[i];
}
printf("%.1lf",ans[n]);
  return 0;
}

Game on Tree

题面翻译

题目描述

给定一棵有根树，结点编号从 $1$ 到 $n$。根结点为 $1$ 号结点。

对于每一次操作，等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 $1$ 号结点后游戏即结束。

要求求出删除所有结点的期望操作次数。

输入格式

第一行，一个正整数 $n$ 表示结点数量。

接下来 $n-1$ 行每行两个数，表示树上的一条连接 $a_i$ 与 $b_i$ 的边 $(a_i,b_i)$

保证给定的数据是一棵树。

输出格式

输出一个实数，表示期望操作次数。答案误差在 $10^{-6}$ 之内则认为正确。

样例解释

在第一个样例中，有两种情况：

一种是直接删除根（即 $1$ 号结点），另一种是先删去 $2$ 号结点，再删除 $1$ 号结点。

操作次数的期望是 $1\times \dfrac12+2\times\dfrac12=1.5$。

在第二个样例中，情况更为复杂。其中有两种情况会将问题转化成第一个样例，而剩下的一种情况会一次全部删除。

操作次数的期望是 $1\times\dfrac13+(1+1.5)\times\dfrac23=\dfrac13+\dfrac53=2$。

题目描述

Momiji has got a rooted tree, consisting of $ n $ nodes. The tree nodes are numbered by integers from $ 1 $ to $ n $ . The root has number $ 1 $ . Momiji decided to play a game on this tree.

The game consists of several steps. On each step, Momiji chooses one of the remaining tree nodes (let's denote it by $ v $ ) and removes all the subtree nodes with the root in node $ v $ from the tree. Node $ v $ gets deleted as well. The game finishes when the tree has no nodes left. In other words, the game finishes after the step that chooses the node number $ 1 $ .

Each time Momiji chooses a new node uniformly among all the remaining nodes. Your task is to find the expectation of the number of steps in the described game.

输入格式

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ — the number of nodes in the tree. The next $ n-1 $ lines contain the tree edges. The $ i $ -th line contains integers $ a_{i} $ , $ b_{i} $ $ (1<=a_{i},b_{i}<=n; a_{i}≠b_{i}) $ — the numbers of the nodes that are connected by the $ i $ -th edge.

It is guaranteed that the given graph is a tree.

输出格式

Print a single real number — the expectation of the number of steps in the described game.

The answer will be considered correct if the absolute or relative error doesn't exceed $ 10^{-6} $ .

样例 #1

样例输入 #1

1
2

2
1 2

样例输出 #1

1	1.50000000000000000000

样例 #2

样例输入 #2

1
2
3

3
1 2
1 3

样例输出 #2

1	2.00000000000000000000

提示

In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are:

$ 1×(1/2)+2×(1/2)=1.5 $ In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are:

$ 1×(1/3)+(1+1.5)×(2/3)=(1/3)+(5/3)=2 $

转载自题解第一篇

简单题意

给出一棵树，每次随机等概率选择一未染黑的点，将它及其子树染黑。问期望多少次操作可以将树全部染黑。

题解

设 $f_i$ 表示 $i$ 号点表示点 $i$ 被选中的次数（显然只可能是 0 或 1）。

则要求的答案就是 $E[\sum f_i]$，即 $f_i$ 的和的期望，

由期望的可加性，有 $E[\sum f_i]=\sum E[f_i]$。

由于 $f_i$ 的取值只能是 0 或 1，则 $f_i$ 的期望就等于 $f_i$ 等于 1 的概率，设为 $p_i$.

则答案为 $\sum p_i$，即每个球被选中的概率的和。考虑随机生成一个操作序列，找到序列中第一个未被染色的节点，并染色这个节点和它的子树中的所有节点，重复这个操作，直到序列中所有节点都被染色。

那么 $i$ 号节点被选中的前提就是在序列中，$i$ 号节点的祖先都在 $i$ 号节点的后面。否则，就会在选择 $i$ 号节点之前选择它的祖先，并且 $i$ 节点就会被染色，而不会被选中。

由于 $i$ 号节点共有 $dep_i-1$ 个祖先，故 $i$ 号节点在这个随机序列中排在所有祖先前面的概率是 $\dfrac 1 {dep[i]}$，故 $i$ 号球被选中的概率是 $\dfrac 1 {dep[i]}$.

故答案为 $\sum\dfrac 1 {dep[i]}$.

根据以上分析，只需要写一个深度优先的函数即可。

采用链式前向星写搜索，中间加答案即可。

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int  i=a;i>=ni--)
using ll=long long;
using namespace std;
int n;
const int N=1e6+100;
void ios()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int cnt;
struct edge
{
    int to;
    int next;
}e[N];
int head[N];
void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
double ans;
void dfs(int u,int fa,double depth)
{
    ans+=1.0/depth;
    for(int i=head[u];i;i=e[i].next)
    {
        if(e[i].to!=fa)
        {
            dfs(e[i].to,u,depth+1);
        }
    }
}
int main()
{
    cin>>n;
    rep(i,1,n-1)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0,1);
    printf("%.8f",ans);
    return 0;

}

条件概率 Probability|Given

题面翻译

有 $n$ 个人要去买东西，第 $i$ 个人买到东西的概率为 $p_i$。现在已知恰好有 $r$ 个人买了东西，在这种条件下，求每个人买到东西的概率。

本题有多组数据，满足测试数据组数不超过 $50$。

对于每组测试数据，共 $n+1$ 行输入。第一行输入两个整数 $n,r$。第 $2$ 到 $n+1$ 行中第 $i$ 行输入 $p_{i-1}$。输入以 0 0 结束。

输出格式：对于每组测试数据，输出 $n+1$ 行。第一行先输出 Case i，其中 $i$ 为当前测试数据的编号。后面 $n$ 行中第 $i$ 行输出第 $i$ 个人买到东西的概率，保留六位小数。

满足 $1\le n\le 20,0\le r\le n,0.1<p_i<1$。

样例输出 #1

Case 1:
0.413043
0.739130
0.847826
Case 2:
0.200000
0.200000
0.200000
0.200000
0.200000

$r$ 个人买了东西 这个事件叫 $E$，第 $i$ 个人买东西 这个事件叫 $E_i$，则要求的是条件概率 $P(E_i|E)$。根据条件概率公式，$P(E_i|E)=\dfrac{P(E_iE)}{P(E)}$。

考虑到 $n\leq20$，于是二进制枚举出每个人是否买东西的情况，算出 $P(E_iE)$ 和 $P(E)$ 即可。

数据很小，可以状压（不会）考虑dfs两次，一次是要考虑，一次是不用考虑，然后计算即可

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int  i=a;i>=ni--)
using ll=long long;
using namespace std;
const int N=1e6+100;
void io()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int n,r;
double p[25];
double pe;
double pei;
void dfs(int x,int d,double _p)
{
//表示到第几个人，第几个人买，和对应的概率
if(d>r)
{
    return ;
}
if(x==n+1)
{
    if(d==r)
    {
        pe+=_p;
    }
return ;
}
dfs(x+1,d+1,_p*p[x]);
dfs(x+1,d,_p*(1-p[x]));
return ;
}
void dfsi(int x,int d,int i,double _p)
{
    if(d>r)
    {
        return ;
    }
    if(x==n+1)
    {
        if(d==r)
        {
            pei+=_p;
        }
    return;
    }
    if(x==i)
    {
        dfsi(x+1,d+1,i,_p*p[x]);
        return ;
    }
    dfsi(x+1,d+1,i,_p*p[x]);
    dfsi(x+1,d,i,_p*(1-p[x]));
    return ;

}
int main()
{
    io();
    int t=0;
while(cin>>n>>r)
{
    if(n==0&&r==0)
    {
        break;
    }
cout<<"Case "<<++t<<":\n";
    rep(i,1,n)
    {
        cin>>p[i];
    }
    pe=0;
    dfs(1,0,1);
    rep(i,1,n)
    {
        pei=0;
        dfsi(1,0,i,1);
        printf("%.6f\n",pei/pe);
    }
}
return 0;
}

WJMZBMR打osu! / Easy

题目背景

原维护队列参见 P1903

题目描述

某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(

我们来简化一下这个游戏的规则

有 $n$ 次点击要做，成功了就是 o，失败了就是 x，分数是按 combo 计算的，连续 $a$ 个 combo 就有 $a\times a$ 分，combo 就是极大的连续 o。

比如ooxxxxooooxxx，分数就是 $2 \times 2 + 4 \times 4 = 4 +16=20$。

Sevenkplus 闲的慌就看他打了一盘，有些地方跟运气无关要么是 o 要么是 x，有些地方 o 或者 x 各有 $50\%$ 的可能性，用 ? 号来表示。

比如 oo?xx 就是一个可能的输入。那么 WJMZBMR 这场 osu 的期望得分是多少呢？

比如 oo?xx 的话，? 是 o 的话就是 oooxx（$9$），是x的话就是 ooxxx（$4$），期望自然就是 $(4+9)/2 =6.5$ 了。

输入格式

第一行一个整数 $n$（$n\le3\times10^5$），表示点击的个数

接下来一个字符串，每个字符都是 o，x，? 中的一个

输出格式

一行一个浮点数表示答案

四舍五入到小数点后 $4$ 位

如果害怕精度跪建议用 long double 或者 extended。

样例 #1

样例输入 #1

1
2

4
????

样例输出 #1

4.1250

先考虑设计状态，我们记期望连续的 o 个数为 $\texttt{len}$，$f_i$ 表示以第 $i$ 个字符结尾的期望得分。

然后，我们考虑如何转移，很明显，转移需要分 o,x,?

当当前字符为 o 时，$f_i=f_{i-1}+[(\texttt{len}+1)^2-\texttt{len}^2]=f_{i-1}+2 \times \texttt{len}+1$，而 $\texttt{len}=\texttt{len}+1$（注意先后顺序，先修改 $f_i$，再修改 $\texttt{len}$，下同）。

当当前字符为 x 时，$f_i=f_{i-1},\texttt{len}=0$。

前两个很显然，重点在 ? 的转移，我们发现 ? 为 x 和 o 的概率是一样的，所以 ? 的转移就相当于把 x 和 o 的转移合在一起，然后乘上概率 $50\%$，即除以 $2$。

也就是说，当当前字符为 ? 时，有：

\[f_i=f_{i-1}+\dfrac{[(\texttt{len}+1)^2-\texttt{len}^2]+0}{2} =f_{i-1}+\texttt{len}+0.5\]

而 $\texttt{len}=\dfrac{\texttt{len}+1}{2}$，$(\texttt{len}+1)^2-\texttt{len}^2$ 和 $\texttt{len}+1$ 是 o 的转移，其他都是 x 的转移，注意 $\texttt{len}$ 的转移应是 $\texttt{len}=\dfrac{(\texttt{len}+1)+0}{2}$，也就是 $\texttt{len}=\dfrac{\texttt{len}+1}{2}$。

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int  i=a;i>=ni--)
using ll=long long;
using namespace std;
const int N=3e5+100;
long double len;
long double f[N];
string s;
void io()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int main()
{
    io();
    int n;
    cin>>n>>s;
    rep(i,1,n)
    {
        if(s[i-1]=='x')
    {
        f[i]=f[i-1];
        len=0;
    }
    else if(s[i-1]=='o')
    {
        f[i]=f[i-1]+2*len+1;
        len++;
    }
    else
    {
        f[i]=f[i-1]+len+0.5;
        len=(len+1)/2;
    }
    }
    printf("%.4Lf",f[n]);
}

绿豆蛙的归宿

题目背景

随着新版百度空间的上线，Blog 宠物绿豆蛙完成了它的使命，去寻找它新的归宿。

题目描述

给出张 $n$ 个点 $m$ 条边的有向无环图，起点为 $1$，终点为 $n$，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果该节点有 $k$ 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 $\frac{1}{k}$ 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入格式

输入的第一行是两个整数，分别代表图的点数 $n$ 和边数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行有三个整数 $u, v, w$，代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。

输出格式

输出一行一个实数代表答案，四舍五入保留两位小数。

样例 #1

样例输入 #1

样例输出 #1

7.00

提示

数据规模与约定

对于 $20\%$ 的数据，保证 $n \leq 10^2$。
对于 $40\%$ 的数据，保证 $n \leq 10^3$。
对于 $60\%$ 的数据，保证 $n \leq 10^4$。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times n$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^9$，给出的图无重边和自环。

我们设状态f[x]表示点x到终点n的期望路径总长，那么显然有f[n]=0

那么这正好符合了“终止状态确定时可用逆推”的策略套路

具体来说：

对于一条有向边,我们假设它由 $x->y$

那么有$f[x]=(\dfrac{1}{degree[x]})*∑f[y]+w[x->y]$

其中$degree[x]$表示x点的度

$(\dfrac{1}{degree[x]})$其实就是概率(p)

转移时的过程怎么实现

既然是个DAG，那么我们可以“倒过来”想

具体来讲，我们反向连边，进行一遍拓扑排序，在拓扑排序的时候进行期望dp的转移

这时候要注意上面的x和y要反过来（因为我们反向连边了）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
const int maxn=100003;
const int maxm=200003;
struct Edge
{
	int from,to,w;
}p[maxm];
int n,m,cnt,head[maxm],in[maxn],dg[maxn];
double f[maxn];//f[x]表示x点到终点n的期望路径总长 
inline void add_edge(int x,int y,int W)//加边
{
	cnt++;
	p[cnt].from=head[x];
	head[x]=cnt;
	p[cnt].to=y;
	p[cnt].w=W;
}
inline void toposort()//拓扑排序
{
	queue <int> q;
	q.push(n);
	while(!q.empty())
		{
			int x=q.front();
			q.pop();
			for(int i=head[x];i;i=p[i].from)
				{
					int y=p[i].to;
					f[y]+=(f[x]+p[i].w)/dg[y];//dp转移 
					if(!(--in[y]))q.push(y);
				}
		}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		{
			int x,y,w;
        	cin>>x>>y>>w;
			add_edge(y,x,w);//反向建图 
			in[x]++,dg[x]++;
		}
	toposort();
	printf("%.2lf\n",f[1]);
	return 0;
}

[国家集训队] 单选错位

题目描述

gx 和 lc 去参加 noip 初赛，其中有一种题型叫单项选择题，顾名思义，只有一个选项是正确答案。

试卷上共有 $n$ 道单选题，第 $i$ 道单选题有 $a_i$ 个选项，这 $a_i$ 个选项编号是 $1,2,3,\ldots,a_i$，每个选项成为正确答案的概率都是相等的。

lc 采取的策略是每道题目随机写上 $1 \sim a_i$ 的某个数作为答案选项，他用不了多少时间就能期望做对 $\sum_{i=1}^n \frac{1}{a_i}$ 道题目。gx 则是认认真真地做完了这 $n$ 道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了：第 $i$ 道题目的答案抄到了答题纸上的第 $i+1$ 道题目的位置上，特别地，第 $n$ 道题目的答案抄到了第 $1$ 道题目的位置上。

现在 gx 已经走出考场没法改了，不过他还是想知道自己期望能做对几道题目，这样他就知道会不会被 lc 鄙视了。

我们假设 gx 没有做错任何题目，只是答案抄错位置了。

输入格式

$n$ 很大，为了避免读入耗时太多，输入文件只有 $5$ 个整数参数 $n, A, B, C, a_1$，由上交的程序产生数列 $a$。下面给出 pascal/C/C++ 的读入语句和产生序列的语句（默认从标准输入读入）：

// for pascal
readln(n,A,B,C,q[1]);
for i:=2 to n do
q[i] := (int64(q[i-1]) * A + B) mod 100000001;
for i:=1 to n do
q[i] := q[i] mod C + 1;


// for C/C++
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
	a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
	a[i] = a[i] % C + 1;

选手可以通过以上的程序语句得到 $n$ 和数列 $a$（$a$ 的元素类型是 $32$ 位整数），$n$ 和 $a$ 的含义见题目描述。

输出格式

输出一个实数，表示 gx 期望做对的题目个数，保留三位小数。

样例 #1

样例输入 #1

3 2 0 4 1

样例输出 #1

1.167

提示

【样例说明】

正确答案	gx的答案	做对题目	出现概率
$\{1,1,1\}$	$\{1,1,1\}$	$3$	$\frac16$
$\{1,2,1\}$	$ {1,1,2}$	$1$	$\frac16$
$\{1,3,1\}$	$ {1,1,3} $	$1$	$\frac16$
$\{2,1,1\}$	$ {1,2,1} $	$1$	$\frac16$
$\{2,2,1\}$	$ {1,2,2}$	$1$	$\frac16$
$\{2,3,1\}$	${1,2,3} $	$0$	$\frac16$

$a = \{2,3,1\}$。

共有 $6$ 种情况，每种情况出现的概率是 $\frac{1}{6}$，gx 期望做对 $\frac{3+1+1+1+1+0}6 = \frac76$ 题。（相比之下，lc 随机就能期望做对 $\frac{11}6$ 题）

对于 $30\%$ 的数据，$n\leq 10, C\leq 10$。

对于 $80\%$ 的数据，$n\leq 10^4, C\leq 10$。

对于 $90\%$ 的数据，$n\leq 5\times 10^5, C\leq 10^8$。

对于 $100\%$ 的数据，$2\leq n\leq 10^7, 0\leq A,B,C \leq 10^8$，$1 \leq a_i \leq 10^8$。

牛客好像有一道题一样的

本题只需要在此基础上进行数据自己创建即可

分类讨论一下。

当$a_i=a_{i+1}$，那么显然随机的答案在第$i+1$题也是随机的。期望为$\frac{1}{a_i}$，也就是$\frac{1}{a_{i+1}}$
当$a_i>a_{i+1}$，只有$\frac{a_{i+1}}{a_i}$的概率答案在$1\sim a_{i+1}$中。所以期望为$\frac{a_{i+1}}{a_i}\times \frac{1}{a_{i+1}}=\frac{1}{a_i}$
当$a_i<a_{i+1}$，由于随机的答案只在$1\sim a_i$中，而第$i+1$题正确答案有$\frac{a_i}{a_{i+1}}$的概率在$1\sim a_i$中，所以期望为$\frac{a_i}{a_{i+1}}\times \frac{1}{a_i}=\frac{1}{a_{i+1}}$

综上，答案就是$\sum^{n}_{i=1}\frac{1}{max(a_i,a_{i+1})}$

#include<bits/stdc++.h>
using namespace std;

const int N=10000010;
int n,a[N];
double ans;

void init()  //题目给出的生成数据的方法
{
	int A,B,C;
	cin>>n>>A>>B>>C>>a[1];
	for (int i=2;i<=n;i++)
		a[i] = ((long long)a[i-1] * A + B) % 100000001;
	for (int i=1;i<=n;i++)
		a[i] = a[i] % C + 1;
}

int main()
{
	init();
	a[n+1]=a[1];  //第1题写第n题的答案
	for (int i=1;i<=n;i++)
		ans+=1/(double)max(a[i],a[i+1]);
	printf("%0.3lf",ans);
	return 0; 
}

考场奇遇

题目背景

本市的某神校里有一个学霸，他的名字叫小明（为了保护主人公的隐私，他的名字都用“小明”代替）。在这次的期中考试中，小明同学走桃花运，在考场上认识了一位女生，她的名字叫小红（同样是为了保护隐私）。

题目描述

英语考试结束了，打完铃，她就主动来找小明说话，一来就要借英语卷子对答案。小明是公认的英语大神，二话不说就把卷子借给了她。小红对了一遍答案，简直是千差万别，她不禁冒出了冷汗。这时，小明走过来，安慰她：“没事，我又不是标准答案，不一定全对。”

已知小明答案的准确率是 $A\%$，一共有 $N$ 道题，给出小红对答案的结果 $S$（一个长为 $N$ 的 01 串，其中 1 表示两人答案一样，0 表示不一样）。为了简化问题，所有题目都是判断题。

请你帮小红写一个程序，计算出她对 $Q$ 题及以上的概率。

（P.S. 小明后来把那张卷子送给了小红，别想多了，不是定情信物）

输入格式

第 $1$ 行，三个正整数 $N,A,Q$。

第 $2$ 行，一个 01 字符串 $S$。

输出格式

一行，一个实数，表示她对 $Q$ 题及以上的概率。（保留 $3$ 位小数）

样例 #1

样例输入 #1

1 2	3 90 2 100

样例输出 #1

0.172

提示

对于 $90\%$ 数据，$N \leq 50, N-5 \leq Q \leq N$。

对于剩下的 $10\%$ 数据，$N \leq 10000, Q = 0$。

f[i] [j] 来表示做i道题中做对j道题的概率

① 上一道题的时候已经做对了j道 那么f[i][j] 就是f[i-1][j]* 这道题做错的概率 

（i-1道时已经做对了j道那么第i道题中对j道一定因为第i道做错了）

②同理相反的情况下 i-1时做对了j-1道 那么要想i道时做对 j道 那么第i道就一定要做对

对于这个问题 小红和小明答案一样时 小明的正确率就是小红的正确率 错误率就是小红的错误率

而当两人答案不一样时，小明的错误率就变成了小红的正确率，而小红的错误率则是小明的正确率

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int  i=a;i>=ni--)
using ll=long long;
using namespace std;
const int N=1e2+100;
double f[N][N];
int n,q;
int a;
double ans;
int main()
{
cin>>n>>a>>q;
    if(n>50) {
        cout<<"1.000";
        return 0;	
    }
double p=a/100.0;
f[0][0]=1;
rep(i,1,n)
{
    char c;
    cin>>c;
    rep(j,0,i)
    {
        if(c=='0')
        {
            f[i][j]=f[i-1][j]*p+f[i-1][j-1]*(1-p);
        }
        else
        {
            f[i][j]=f[i-1][j-1]*p+f[i-1][j]*(1-p);
        }
    }
}
    rep(i,q,n)
    {
        ans+=f[n][i];
    }
    printf("%.3lf",ans);


}

正确答案	gx的答案	做对题目	出现概率
\(\{1,1,1\}\)	\(\{1,1,1\}\)	\(3\)	\(\frac16\)
\(\{1,2,1\}\)	$ {1,1,2}$	\(1\)	\(\frac16\)
\(\{1,3,1\}\)	$ {1,1,3} $	\(1\)	\(\frac16\)
\(\{2,1,1\}\)	$ {1,2,1} $	\(1\)	\(\frac16\)
\(\{2,2,1\}\)	$ {1,2,2}$	\(1\)	\(\frac16\)
\(\{2,3,1\}\)	${1,2,3} $	\(0\)	\(\frac16\)