目录
参考文献
此垃圾博客参考于一下大佬文献：
- 你谷日报吼：https://45475.blog.luogu.org/mathematical-expectation
- 每道题的题解。
- 百度百科
貌似就这些了QMQ
概率初解
概率初解
概率其实很迷。
比如你扔一个六面骰子，然后扔到\(3\)的概率是\(\frac{1}{6}\)。
度娘的话：
概率，亦称“或然率”，它是反映随机事件出现的可能性（likelihood)大小。
随机事件是指在相同条件下，可能出现也可能不出现的事件。
例如，从一批有正品和次品的商品中，随意抽取一件，“抽得的是正品”就是一个随机事件。
设对某一随机现象进行了n次试验与观察，其中A事件出现了m次，即其出现的频率为m/n。
经过大量反复试验，常有m/n越来越接近于某个确定的常数（此论断证明详见伯努利大数定律）。
该常数即为事件A出现的概率，常用P (A) 表示。概率抽象理解就行了。
期望
期望的定义与性质
以下摘自日报（因为实在找不到比日报更好的讲解与证明了）：
期望定义
日常生活中，我们每做一件事，都有对它的期望，这里的期望不仅仅只结果的胜负之类，也可以与状态有关。但在OI中，一般指的就是达到结果的期望，最朴素的计算是每次可能结果的概率乘以其结果的总和
这是最基本的数学特征。
广义下的定义：一次随机抽样中所期望的某随机变量的取值。
数学定义：
也许许多人会说期望很像平均数，因为有些期望的计算公式可以化成平均数。
期望性质
- 设X是随机变量，C是常数，则 E(CX)=C×E(X)E(CX)=C\times E(X)E(CX)=C×E(X)
简单证明一下：
设\(x\)的多个随机变量为
\(Ca_1,Ca_2,Ca_3...Ca_nCa1,Ca2,Ca3...Can\)
对应的出现概率为
\(p_1,p_2,p_3...p_np1,p2,p3...pn\)
那么对应的求期望的式子
\(E(CX)=C\sum_{i=1}^{n}(a_i\times p_i)\)
(\(C\)提出来)
由于：
\(E(CX)=\sum_{i=1}^{n}(a_i\times p_i)\)
所以
\(E(CX)=C\times E(X)\)
- 设\(X\)，\(Y\)是任意两个随机变量，则有 \(E(X+Y)=E(X)+E(Y)\)（这个很好想）。
- 设\(X\)，\(Y\)是相互独立的随机变量，则有\(E(XY)=E(X)\times E(Y)\)（你可以把\(E(XY)\)拆开，然后用乘法分配律就可以得出结论了）。
- 设\(C\)为常数，则 \(E(C)=C\)。
证明性质
证明这些性质对后面做题目都很有帮助。
同时注意一下，期望题目许多都与级数求和这种毒瘤东西挂钩。
性质1
现在你知道\(x(-1<x<1)\)，请求出\(1+x+x^{2}+x^{3}+x^{4}+...\)的收敛值。
关于收敛的定义上网查吧，大概意思就是说这个式子在无限的情况下会无限接近于收敛值。
我们设\(f(x)=1+x+x^{2}+x^{3}+x^{4}+...\)
\(xf(x)=x+x^{2}+x^{3}+x^{4}+...\)
\(f(x)-xf(x)=1\)
\(f(x)=\frac{1}{1-x}\)
但是只有在\(-1<x<1\)才收敛，我也不会证，抽象理解。
性质2
现在你知道拿到一个红球的概率是\(\frac{1}{x}(x>1)\)，那么期望拿多少个球才能拿到这个东西呢？
我们知道假设我们拿了\(t\)个球才拿到的话，那么这种情况的概率就是\((\frac{x-1}{x})^{t-1}*\frac{1}{x}\)（\((\frac{x-1}{x})^{t-1}\)为前\(t-1\)个球拿到不是红球的概率）。
那么总体上的期望就是：\(\frac{1}{x}+2(\frac{x-1}{x})\frac{1}{x}+3(\frac{x-1}{x})^2\frac{1}{x}+...\)，我们先把\(\frac{1}{x}\)提出来。
然后\(f(x)=1+2(\frac{x-1}{x})+3(\frac{x-1}{x})^2+4(\frac{x-1}{x})^3+...\)。
\((\frac{x-1}{x})f(x)=(\frac{x-1}{x})+2(\frac{x-1}{x})^2+3(\frac{x-1}{x})^3+4(\frac{x-1}{x})^4+...\)
然后上式减下式：
\((\frac{1}{x})f(x)=1+(\frac{x-1}{x})+(\frac{x-1}{x})^2+(\frac{x-1}{x})^3+(\frac{x-1}{x})^4+...\)
我们后面的式子可以套用性质1：\((\frac{1}{x})f(x)=x\)
\(f(x)=x^2\)，然而外面还有一个\(\frac{1}{x}\)，所以我们期望拿\(x\)个球就可以拿到了。（我不会证收敛性，但是\(x>1\)凭感觉都知道是收敛的吧。）
虽然我一开始SSBB的认为拿\(x\)拿到一个红球，期望概率是\(\frac{1}{x}\)，那么反过来也一样，但是其实仔细看看会发现不一样，如果你玩多了文字游戏的话。
当然我们在这里也证了。
题目练习
期望性质这些经常是撺在一起的，所以单独开一版吧。
将会从易到难依次排开。
例题
简单期望
题面
贝茜喜欢玩棋盘游戏和角色扮演游戏，所以她说服了约翰开车带她去小商店.在那里她买了三个骰子.这三个不同的骰子的面数分别为s1 s2 s3
对于一个有S个面的骰子每个面上的数字是1，2,3，...，S.每个面（上的数字）出现的概率均等.贝茜希望找出在所有“三个面上的数字的和”中，哪个和的值出现的概率最大.
现在给出每个骰子的面数，需要求出哪个所有“三个面上的数字的和”出现得最频繁.如果有很 多个和出现的概率相同，那么只需要输出最小的那个. 数据范围： （2＜S1<＝20；2 <＝S2<＝20；2 <＝S3<＝40）
输入输出样例
输入 #1 复制
3 2 3
输出 #1 复制
5
说明/提示
Here are all the possible outcomes.
1 1 1 -> 3
1 2 1 -> 4
2 1 1 -> 4
2 2 1 -> 5
3 1 1 -> 5
3 2 1 -> 6
1 1 2 -> 4
1 2 2 -> 5
2 1 2 -> 5
2 2 2 -> 6
3 1 2 -> 6
3 2 2 -> 7
1 1 3 -> 5
1 2 3 -> 6
2 1 3 -> 6
2 2 3 -> 7
3 1 3 -> 7
3 2 3 -> 8
Both 5 and 6 appear most frequently (five times each), so 5 is the answer.特殊要求：\(O(1)\)解决。
是不是瞬间感觉恶心的一批！
首先，我们知道三个加起来的期望等于三个分别的期望加起来。（期望的性质）
那么我们很容易证到期望就为\(\frac{a+b+c+3}{2}\)。
但是为什么期望是出现概率最大的呢？
从统计学的角度上谈，应该是从每个数字出现的概率都是一样的出发去想这个问题。
而且因为每个和的期望化成函数图像长这样：/￣。
所以期望确实出现次数最多的，但是不是最小的。
需要特判，就是当\(a>b+c\)时，答案为\(b+c+1\)（这个仔细想想就知道了）。
当然这道题目要是要求变成\(O(1)\)期望题的话应该绿题起步吧。
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
if(c>=a+b+1)printf("%d\n",a+b+1);
else if(b>=a+c+1)printf("%d\n",a+c+1);
else if(a>=b+c+1)printf("%d\n",b+c+1);//以上是特判
else printf("%d\n",(a+b+c+3)/2);
return 0;
}如果有方法证明期望是最多的，请在评论留言或者私信，谢谢。
概率DP
有许多题是递推，所以我不是很清楚哪些题是DP，但是这道题目应该是的，同时因为我太弱了，下面的递推说是DP不要介意。
题面过恶心，我就不复制了。
但是其实挺好设计状态的：\(f[i][0/1]\)表示的是到了第\(i\)个时间段，\(0\)表示不申请，\(1\)表示申请的期望（不管失败或成功）。
不要把失败和成功的拆开来，我当时就就是拆开来了，然后发现失败和成功转移的时候也许会从不同的情况转移过来，导致失败成功加起来的期望小于正确答案，这道题目的最小期望要求的是成功失败从同一情况转移后的最小期望。
当然，距离\(dis\)不是一个Floyd就能解决的事情吗。
然后接下来的转移其实也就很简单了，我们设\(a_0=a[i-1][0],a_1=a[i-1][1],b_0=a[i][0],b_1=a[i][1],c_0=su[i-1],c_1=su[i]\)。（\(a[i][0]\)表示第\(i\)时间段原来的教师，\(a[i][1]\)表示申请成功后的教师，\(su\)表示成功的概率）。
\(f[i][0]=min(f[i-1][0]+dis[a_0][b_0],f[i-1][1]+dis[a_0][b_0]*(1-c_0)+dis[a_1][b_0]*c_0)\)
\(f[i][1]=min(f[i-1][0]+dis[a_0][b_0]*(1-c_1)+dis[a_0][b_1]*c_1,f[i-1][1]+(dis[a_0][b_0]*(1-c_0)+dis[a_1][b_0]*c_0)*(1-c_1)+(dis[a_0][b_1]*(1-c_0)+dis[a_1][b_1]*c_0)*c_1)\)
#include<cstdio>
#include<cstring>
#define N 2100
#define M 310
using namespace std;
typedef long long LL;
template <typename T>
inline T mymin(T x,T y){return x<y?x:y;}
int a[N][2],n,m,ch/*修改次数*/,di/*点*/;
double b[N],dis[M][M],f[N][N][2];
int main()
{
scanf("%d%d%d%d",&di,&ch,&n,&m);if(ch>di)ch=di;
for(int i=1;i<=di;i++)scanf("%d",&a[i][0]);
for(int i=1;i<=di;i++)scanf("%d",&a[i][1]);
for(int i=1;i<=di;i++)scanf("%lf",&b[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)dis[i][j]=29999999999.0;
dis[i][i]=0;dis[0][i]=dis[i][0]=0;
}
for(int i=1;i<=m;i++)
{
int x,y;double c;scanf("%d%d%lf",&x,&y,&c);
if(c<dis[x][y])dis[x][y]=dis[y][x]=c;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)dis[j][k]=mymin(dis[i][j]+dis[i][k],dis[j][k]);
}
}//可爱的Floyd
for(int i=0;i<=di;i++)
{
for(int j=0;j<=ch;j++)
{
for(int k=0;k<=1;k++)f[i][j][k]=29999999999.0;
}
}
f[1][0][0]=f[1][1][1]=0;
for(int i=2;i<=di;i++)f[i][0][0]=f[i-1][0][0]+dis[a[i-1][0]][a[i][0]];
for(int i=2/*1的预处理了*/;i<=di;i++)
{
int ed=mymin(i,ch),x1=a[i-1][0],x2=a[i-1][1],x3=a[i][0],x4=a[i][1];
for(int j=1;j<=ed;j++)
{
f[i][j][0]=mymin(f[i-1][j][0]+dis[x1][x3],f[i-1][j][1]+dis[x1][x3]*(1-b[i-1])+dis[x2][x3]*b[i-1]);
f[i][j][1]=mymin(f[i-1][j-1][0]+dis[x1][x3]*(1.0-b[i])+dis[x1][x4]*b[i],f[i-1][j-1][1]+(dis[x1][x3]*(1-b[i-1])+dis[x2][x3]*b[i-1])*(1-b[i])+(dis[x1][x4]*(1-b[i-1])+dis[x2][x4]*b[i-1])*b[i]);
}
}
double ans=f[di][0][0];
for(int i=1;i<=ch;i++)ans=mymin(mymin(f[di][i][0],f[di][i][1]),ans);
printf("%.2lf",ans);
return 0;
}条件期望
条件期望什么意思，比如说假设你不断扔一个等概率的六面骰子，直到扔出\(6\)停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。
一看，期望值\(3\)呀，但是并不对，因为骰到\(1,3,5\)的情况的期望也算进去，所以答案并不是\(3\)。
但是因为只要骰到\(1,3,5\)，情况就终止，所以一般条件期望会比较小。
毕竟如果你并没有投到奇数的话，骰到\(6\)的概率也是挺大的。
我们在这里算一下（非严格写法，因为我没学过）：
设\(a=\frac{1}{6},b=\frac{6-3-1}{6}=\frac{2}{6}=\frac{1}{3},c=\frac{3}{6}=\frac{1}{2}\)
期望为\((a+2*b*a+3*b^2*a+4*b^3*a+5*b^4*a...)+(c+2*b*c+3*b^2*c+4*b^3*c+..)\)，我们把第一个括号的\(a\)提出来，那么我们再设\(f(b)=1+2b+3b^2+4b^3+5b^4+...\)。
\(bf(b)=b+2b^2+3b^3+...\)
\((1-b)f(b)=1+b+b^2+b^3+...\)
套用性质1得：
\((1-b)f(b)=\frac{1}{1-b}\)
所以\(f(b)=\frac{1}{(1-b)^2}\)
那么第一个括号就是\(\frac{a}{(1-b)^2}\)，而我们自然就知道了第二个括号：\(\frac{c}{(1-b)^2}\)，所以期望就是\(\frac{a+c}{(1-b)^2}=\frac{3}{2}\)。
后面大家就会看到一道友(du)善(liu)的条件期望的题目了。
题目
期望初练
我们很容易发现对于第\(i\)个位置，他正确的概率是\(\frac{min(a[i],a[i-1])}{a[i]*a[i-1]}=\frac{1}{max(a[i],a[i-1])}\)（第一个分式即情况数乘每一种情况发生的概率）。
而且根据前面期望的性质我们知道对于两个随机的\(x,y\)，\(E(x+y)=E(x)+E(y)\)。
所以我们可以把所有的期望加起来就是答案了，也许有人会说如果有\(n-1\)道题目对了的话，那么剩余那道也是对的，那是不是代表这之间有什么不可告人的联系呢？
不是，仔细想想就知道，我们算的概率是部分概率，不会对其他的计算有什么影响。
#include<cstdio>
#define N 11000000
using namespace std;
int a[N],n,A,B,C;
double ans=0;
inline int mymax(int x,int y){return x>y?x:y;}
int main()
{
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;
a[n+1]=a[1];
for(int i=1;i<=n;i++)ans+=1.0/mymax(a[i],a[i+1]);
printf("%.3lf\n",ans);
return 0;
}没错，17行代码AC掉了一道蓝题，你敢信。
二次期望
这道题目！二次，难道是黑题。蓝题？
别紧张，放松，我们现在设\(a\)数组表示以第\(i\)位为结尾期望能有多少个连续的\(o\)。
那么转移也就很好想了。
\(a[i]=(1+a[i-1])*?+0*(1-?)\)，\(?\)是什么，就是这个位置是\(o\)的概率
而\(b[i]\)表示的就是以第\(i\)个数字为结尾的期望\(1\)的个数的平方。
那岂不是就是\(b[i]=a[i]^2\)，那岂不是很快就可以AC蓝题了，这么简单，我要去考提高组！
然后......
图片来自日报。
我们上面都说了，满足\(E(xy)=E(x)E(y)\)是要\(x,y\)互相独立，这里都是两个相同的数字了！
你自己试试乘法分配律看看符不符合。
所以，吸取了前人的经验，又写了一个DP转移方程。
\(b[i]=(b[i-1]+2*a[i-1]+1)*?\)（注意\((x+1)^2=x^2+2x+1\)）
于是又交了一遍。
图片来自日报。
怎么又错了，不应该呀，DP推对了呀。
但是\(b[n]\)并不是答案，于是我们把他的定义改一下，变成前\(i\)个的期望得分。
\(b[i]=(b[i-1]+2[i-1]+1)*?+b[i-1]*(1-?)\)
化简后答案为：
\(b[i]=b[i-1]+(2[i-1]+1)*?\)
于是我们再次以很短的代码AC了一道蓝题。
#include<cstdio>
#include<cstring>
#define N 310000
using namespace std;
int n;
char st[N];
double a[N],f[N],ff[N];
int main()
{
scanf("%d",&n);
scanf("%s",st+1);
for(int i=1;i<=n;i++)
{
if(st[i]=='x')a[i]=0;
else if(st[i]=='o')a[i]=1;
else a[i]=0.5;
}
for(int i=1;i<=n;i++)f[i]=(f[i-1]+1)*a[i],ff[i]=(ff[i-1]+f[i-1]*2+1)*a[i]+ff[i-1]*(1-a[i]);
printf("%.4lf\n",ff[n]);
return 0;
}简单期望题
我们可以发现已经拿到\(x\)张邮票后，拿到新一张的邮票的概率为\(\frac{n-x}{n}\)。
那么根据我们之前的性质2，所以拿到新的邮票的期望就是\(\frac{n}{n-x}\)。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
LL a,b,c;
int n;
inline LL gcd(LL x,LL y){return !x?y:gcd(y%x,x);}
void jia(LL x,LL y)//a/b+x/y
{
LL z=gcd(y,c),now=c;
b*=y/z;c*=y/z;x*=now/z;y*=now/z;
b+=x;z=gcd(b,c);
b/=z;c/=z;
a+=b/c;b%=c;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
a=b=0;c=1;
for(int i=1;i<=n;i++)
{
LL x=n,y=i,z=gcd(n,i);
jia(x/z,y/z);
}
if(!b)printf("%lld\n",a);
else//输出
{
LL x=a,y=c;int len=1,lem=0;
while(x)len++,x/=10;
for(int i=1;i<=len;i++)printf(" ");
printf("%lld\n",b);
printf("%lld ",a);
while(y)lem++,y/=10;
for(int i=1;i<=lem;i++)printf("-");
printf("\n");
for(int i=1;i<=len;i++)printf(" ");
printf("%lld\n",c);
}
}
return 0;
}转化题目意思
我们刚开始也许会摸不到头绪，然后我们接着就发现了一件事情，买\(x\)张邮票的花费是\(\frac{x(x+1)}{2}\)。
咦，这不是二次期望吗，根据以前的经验，我们继续把他化成\(\frac{x^2+x}{2}\)，而常数可以直接提出来，所以我们只要分别求出\(x^2\)和\(x\)的期望即可。
但是怎么求？
\(x\)的求法很简单，前面讲过，不再赘述。
而\(x^2\)我们就一时间摸不到脑袋了。
于是我们就想到了微积分。
很容易想到期望式子为：
\(b[i]=(b[i-1]+2a[i-1]+1)\frac{n-x}{n}+(b[i-1]+4a[i-1]+4)\frac{x}{n}\frac{n-x}{n}+(b[i-1]+6a[i-1]+9)(\frac{x}{n})^2\frac{n-x}{n}+...\)
\(=\frac{n-x}{n}b[i-1](1+\frac{x}{n}+(\frac{x}{n})^2+...)+2a[i-1]\frac{n-x}{n}(1+2\frac{x}{n}+3(\frac{x}{n})^2+...)+\frac{n-x}{n}(1+4\frac{x}{n}+9(\frac{x}{n})^2+...)\)
那么对于第\(1\)项，我们很容易算出就是\(b[i-1]*1=b[i-1]\)，而对于第二项，我们也可以很容易算出答案为\(2(\frac{n}{n-x})a[i-1]\)，对于最后一项，我们发现\((x+1)^2-x^2=2x+1\)，所以我们只需要比以往多减一次就行了。
\(f(x)=1+4\frac{x}{n}+9(\frac{x}{n})^2+...\)
\(\frac{x}{n}f(x)=(\frac{x}{n})+4(\frac{x}{n})^2+9(\frac{x}{n})^3+...\)
\(\frac{n-x}{n}f(x)=1+3\frac{x}{n}+5(\frac{x}{n})^2+...\)
\(\frac{x}{n}\frac{n-x}{n}f(x)=\frac{x}{n}+3(\frac{x}{n})^2+5(\frac{x}{n})^3+...\)
\((\frac{n-x}{n})^2f(x)=1+2\frac{x}{n}+2(\frac{x}{n})^2+...\)
\(\frac{x}{n}(\frac{n-x}{n})^2f(x)=\frac{x}{n}+2(\frac{x}{n})^2+2(\frac{x}{n})^3+...\)
\((\frac{n-x}{n})^3f(x)=1+\frac{x}{n}=\frac{n+x}{n}\)
\(f(x)=\frac{(n+x)n^2}{(n-x)^3}\)
那么第二项就为\(\frac{(n+x)n}{(n-x)^2}\)。
然后我们只要把这一坨加在一起就行了。
#include<cstdio>
#include<cstring>
#define N 11000
using namespace std;
double a[N],b[N];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
double x=n*1.0/(n-i+1);//因为目前拿了i-1张邮票
a[i]=a[i-1]+x;
b[i]=b[i-1]+a[i-1]*2*x+((n+i-1)*1.0/n)*x*x;
}
printf("%.2lf\n",(a[n]+b[n])/2);//答案
return 0;
}三次期望
不，其实这次是紫题。
有了前次的经验，我们立马就设下了\(a,b,c\)数组，分别表示以\(i\)为结尾的\(1\)的个数的期望、平方期望、次方期望，\(f\)表示成功概率。
\(a[i]=(a[i-1]+1)*f[i]\)
\(b[i]=(b[i-1]+2a[i-1]+1)*f[i]\)
\(c[i]=(c[i-1]+3b[i-1]+3a[i-1]+1)*f[i]\)
难道我又要AC紫题了。
貌似哪里不对，哦，\(c\)数组要改改定义，定义为\(1-i\)的期望得分。
那么：
\(c[i]=(c[i-1]+3b[i-1]+3a[i-1]+1)*f[i]+c[i-1]*(1-f[i])=c[i-1]+(3b[i-1]+3a[i-1]+1)*f[i]\)。
#include<cstdio>
#include<cstring>
#define N 110000
using namespace std;
double a[N],b[N],c[N],s[N];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf",&s[i]);
for(int i=1;i<=n;i++)
{
a[i]=(a[i-1]+1)*s[i];
b[i]=(b[i-1]+2*a[i-1]+1)*s[i];
c[i]=c[i-1]+(3*b[i-1]+3*a[i-1]+1)*s[i];
}
printf("%.1lf\n",c[n]);
return 0;
}
当然，如果扩展到\(k\)次的话，那么我们就只能用二项式定理使得时间复杂度为\(O(nk^2)\)，貌似用\(NTT\) or \(FFT\)可以使得时间复杂度为\(O(nklogk)\)。
怎么扩展，在这里提一下。
就是对于\(a[i][j]\)，表示\(i\)结尾，\(j\)次方的期望，那么根据二项式定理很容易知道：\(a[i][j]=a[i-1][j]*C_j^0+a[i-1][j-1]*C_j^1+a[i-1][j-2]*C_j^2+a[i-1][j-3]*C_j^3+...+1*C^j_j\)
我们也许不能用\(FFT\)加速计算这个式子，但是我们可以加速运算\(a[i]\)的所有\(j\)的式子，使其加速到\(klogk\)。
具体方案：
我们把组合数拆开：\(C_j^x=\frac{j!}{x!(j-x)!}\)，不难对于发现，对于每个式子，\(j!\)是定值，提出来，然后对于\(x!(j-x)!\)，不难发现对于\(a[i][j-x]\)，他的系数永远是\(\frac{1}{x!(j-x)!}\)（\(j!\)已提出来），对于固定的\(j-x\)而言，\(\frac{1}{(j-x)!}\)可以作为他的系数，而\(x!\)则是另外一个多项式的系数，然后乘在一起加到这一项。
即(这里直接用\(x\)代替\(j-x\))：\(\frac{a[i][x]}{x!}*\frac{1}{y!}\)，加到新的多项式的第\((x+y)\)项，像极了转积，不就是转积。
我们只需要定义两个多项式乘起来，就可以得到对于\(a[i]\)的每个\(j\)了。
被师兄D飞了QAQ。
条件期望
这道题目我们需要明白一个事情，就是不管从哪个地方开始的魔法的概率都是一样的。
你可以抽象的理解为：你和同学有一个红球和一坨白球，随机抽取，难道有可能因为先后顺序导致概率不同吗？
比较严谨的证明：
不难发现从\(1\)开始的魔法概率是：\(\frac{a_1a_2a_3a_4a_5a_6a_7}{n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)}\)
一下证明铐自https://www.luogu.org/blog/command-block/solution-p3802大佬的博客：
\((a_1/N)(7!∗(a_1−1)/(N−1)∗a_2/(N−2)∗a_3/(N−3)...a_7/(N−7))+\)
\((a_2/N)(7!*a_1/(N-1)*(a_2-1)/(N-2)*a_3/(N-3)...a_7/(N-7))+\)
\(……\)
\((a_7/N)(7!*a_1/(N-1)*a_2/(N-2)*a_3/(N-3)...(a_7-1)/(N-7))\)
设 \(∏a_i=R\)
也就是
\(=7!/N/(N-1)/(N-2)/.../(N-7)*((a_1-1)R+(a_2-1)R+...+(a_7-1)R)\)
\(=7!/N/(N-1)/(N-2)/.../(N-7)*(N-7)R\)
\(=7!/N/(N-1)/(N-2)/.../(N-6)*R\)
\(=7!*a_1/N*a_2/(N-1)*a_3/(N-2)...a_7/(N-6)\)
也就是“在第8次触发一个七重奏的概率”与“所以在第7次就触发一个七重奏的概率”相等。
同理“在第任意次触发一个七重奏的概率”与“所以在第7次就触发一个七重奏的概率”相等
那么答案就是\(\frac{a_1a_2a_3a_4a_5a_6a_7}{n(n-1)(n-2)(n-3)(n-4)(n-5)}\)
#include<cstdio>
#include<cstring>
using namespace std;
double ans=1.0;
int a[10],s;
int main()
{
for(int i=1;i<=7;i++){scanf("%d",&a[i]);s+=a[i];}
if(s<7){printf("0.000\n");return 0;}//特判
for(int i=1;i<=7;i++)ans*=(a[i]*1.0)/((s-i+1)*1.0);
printf("%.3lf\n",ans*7*6*5*4*3*2*(s-6)*1.0);
return 0;
}
当期望到了图上
很明显的\(DAG\) \(DP\)
这道题目我们先考虑\(f[i]\)表示的是\(1-i\)的路径期望长度。
但是我们发现了一个问题，一条路径中边的概率的影响是对后面有影响，而不是对前面，这样就使得有后效性了。
那么我们就设\(f[i]\)表示\(i-n\)然后倒着\(DP\)吗。
但是我比较喜欢找边的期望次数。
而边的期望次数可以直接找起点的期望次数求出来，设\(f[i]\)表示\(i\)被期望经过几次。
则对于边\((x->y)\)：
\(f[y]+=\frac{f[x]}{d[x]}\)
特殊的：\(f[1]=1\)
#include<cstdio>
#include<cstring>
#define N 110000
#define M 210000
using namespace std;
struct node
{
int x,y,c,next;
}a[M];int len,last[N];
inline void ins(int x,int y,int c){a[++len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
inline int mymin(int x,int y){return x<y?x:y;}
int in[N],out[N],n,m;
double dp[N];
int list[N],top;
void solve()//拓扑序
{
list[++top]=1;
int now=1;
while(top<n)
{
int xx=top+1;
for(int i=now;i<xx;i++)
{
int x=list[i];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;in[y]--;
if(!in[y])list[++top]=y;
}
}
now=xx;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);in[y]++;out[x]++;
}
solve();
dp[1]=1.0;
for(int i=1;i<=n;i++)
{
int x=list[i];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
dp[y]+=dp[x]/out[x];
}
}
double ans=0;
for(int i=1;i<=m;i++)ans+=a[i].c*dp[a[i].x]/out[a[i].x];
printf("%.2lf\n",ans);
return 0;
}
图上进阶
无向图怎么做？我们照样求出每个点的期望次数，每条边的期望次数是可以由两端的端点得到的。
对于\(f[n]=0,f[1]+=1\)，为什么，因为是由\(1\)出发的，同时因为到了\(n\)就停止，所以即使有经过次数，为了防止计算错边的期望次数，所以我们不考虑进去，同时因为终点不会跑到其他的点，设成\(0\)可以认为就是不会走出来。
对于边\((x,y)\)，有：
\(f[y]+=\frac{f[x]}{d[x]}\)。
对于\((y,x)\)同理。
那么我们发现有许多的未知元，未知元！那就高斯消元吗！
同时证明一个定理：
\(a<=b<=c<=d\)
那么\(ac+bd>=ad+bc\),\(ab+cd>=ad+bc\)
第一个不等式中，我们用减法计算：
\(ad+bc-ac-bd=a(d-c)+b(c-d)=(a-b)(d-c)<=0\)，所以\(ac+bd>=ad+cd\)
第二个不等式同理：
\(ad+bc-ab-cd=a(d-b)+c(b-d)=(a-c)(d-b)<=0\)，所以\(ab+cd>=ad+bc\)
所以我们只需要把编号大的给期望经过次数小的边就可以算出最小答案了。
//高斯消元为什么要选最大的元作为主元，就是因为当误差为1e-9时，如果乘的数字越大，误差也就会越大
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 510
#define M 510000
using namespace std;
struct node
{
int x,y,next;
}a[M];int len,last[N],in[N],out[N];
inline void ins(int x,int y){in[y]++;out[x]++;a[++len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int n,m;
double ff[N][N],f[N];//为高斯消元做准备。
//一个n-1元的方程
double aa[M];//表示边的期望经过次数
void solve()
{
for(int i=1;i<n;i++)
{
int mmax=i;
for(int j=i+1;j<n;j++)if(ff[j][i]>ff[mmax][i])mmax=j;
if(mmax!=i)swap(ff[i],ff[mmax]);//交换出最大的。
for(int j=i+1;j<n;j++)
{
double tmp=ff[j][i]/ff[i][i];
for(int k=i;k<=n;k++)ff[j][k]-=ff[i][k]*tmp;
}
}
for(int i=n-1;i>=1;i--)
{
f[i]=ff[i][n]/ff[i][i];
for(int j=1;j<i;j++)ff[j][n]-=ff[j][i]*f[i];
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
for(int i=1;i<n;i++)
{
ff[i][i]=1;//表示自己的期望的系数为1
if(i==1)ff[i][n]=1.0;
for(int k=last[i];k;k=a[k].next)
{
int y=a[k].y;
if(y!=n)
{
ff[i][y]=-1.0/out[y];//因为如果是y=n的话，但是我们已经知道f[n]=0了，就不需要了
//f[x]+=f[y]/out[y] f[x]-(1/out[y])f[y]=0
}
}
}
//构造方程
solve();//解方程
for(int i=1;i<=len;i++)aa[(i+1)/2]+=f[a[i].x]/out[a[i].x];
sort(aa+1,aa+m+1);
double ans=0;
for(int i=1;i<=m;i++)ans+=aa[i]*(m-i+1);//大配小才是真的小
printf("%.3lf\n",ans);
return 0;
}
毒瘤题在树上
分数模不就是求逆元的事，求逆元不就是快速幂的事。
求\(x-y\)的期望步数？
我们假设固定了终点，然后求整棵树到他的期望步数。
就把\(1\)当成终点，以他建立有根树。
设\(f[x]\)表示\(x\)到父亲的期望步数，特殊的，\(f[1]=0\)
\(f[x]=\frac{1}{d[x]}+\sum_{y∈son[x]]}(f[x]+1+f[y])*\frac{1}{d[x]}\)
\(f[x]=1+\sum_{y∈son[x]]}\frac{f[y]}{d[x]}+\frac{f[x]*(d[x]-1)}{d[x]}\)
\(\frac{f[x]}{d[x]}=1+\sum_{y∈son[x]]}\frac{f[y]}{d[x]}\)
\(f[x]=d[x]+\sum_{y∈son[x]]}f[y]\)
咦，这不是\(x\)子树内所以节点的度数和吗？
新发现！
对于每个子树内的节点都要经过\(x\),所以\(x\)对答案的贡献就是\(f[x]sz[x]\)。
设\(R\)为树内所有节点的度数和。
我们发现终点只要在\(x\)的子树外，\(f\)和\(sz\)都是原来那样，有\(sz[x]\)种这种情况。
如果终点在\(x\)，那么\(f[x]=0\)，无贡献。
如果终点在\(x\)的儿子\(y\)的子树内，那么把整棵树转一下：\(sz[x]=sz[1]-sz[y],f[x]=R-f[y]\)，而且共有\(sz[y]\)种这种情况。
时间复杂度\(O(n+m)\)，这不就好起来了吗！！！
#include<cstdio>
#include<cstring>
#define N 110000
#define M 210000
using namespace std;
typedef long long LL;
struct node
{
int y,next;
}a[M];int len,last[N];
inline void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
LL f[N],d[N],sumd,fa[N],mod=998244353,sz[N];
int n;
void dfs(int x)
{
f[x]=d[x];sz[x]++;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[x])
{
fa[y]=x;
dfs(y);
f[x]+=f[y];
sz[x]+=sz[y];
}
}
}
inline LL mypow(LL x,LL y)//求逆元
{
LL ans=1;
while(y>1)
{
if(y&1)ans*=x,ans%=mod;
y>>=1;x=(x*x)%mod;
}
return (ans*x)%mod;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);d[x]++;d[y]++;sumd+=2;
}
dfs(1);f[1]=0;
LL ans=0;
for(int i=1;i<=n;i++)
{
ans+=f[i]*sz[i]*(n-sz[i]);ans%=mod;
for(int k=last[i];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[i])ans+=(sumd-f[y])*(n-sz[y])*sz[y],ans%=mod;
}
}
printf("%lld\n",(ans*mypow(((LL)n*n)%mod,mod-2))%mod);
return 0;
}
二次期望题
这道题目不是很难，先考虑\(1\)次的。
我们考虑从\(1\)开始编号，不习惯从\(0\)开始编。
我们来看一下，根据题意，每个点只能连到前面的点，我们很难考虑到每个图中每个点的贡献，我们可以考虑每个点对答案的总贡献。
对于第\(x\)个点，原本他要连向后面，\(d[x]=1\)，同时后面的点可以连向他，有个概率，那么我们为什么不能把所有情况列举出来然后算出期望呢？
然而时间复杂度巨大，我们就考虑从式子上出发：
对于\(x\)，期望表示\(x\)的度数期望对答案做的贡献。
\((\frac{x-1}{x}\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+2(\frac{1}{x}\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+2(\frac{x-1}{x}\frac{1}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+...\)
看到这么多的式子，我激动的哇的一下哭了。
这个式子化个鬼呀，一点都不会做，但是仔细想想，貌似我除了化式子还有别的出路，就是递推！
我们可以发现，如果不考虑\(x+1\)连到\(x\)的情况（即只考虑\(x+2\)到\(n\)的连边情况）的话，\(x+1\)与\(x\)对答案的贡献是一样的，那么我们就可以\(f[x]=f[x+1]\)？
然后我们可以从式子上继续扩展，如果\(x+1\)不连到\(x\)的话，即：\(f[x]=f[x+1]*\frac{x-1}{x}\)。
但是如果连到的话，在期望的计算公式中所有的系数都要加\(1\)（即度数\(+1\)），我们用乘法分配律把所有的\(1\)提出来易知：
\(f[x]=f[x+1]*\frac{1}{x}+\frac{1}{x}((\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+(\frac{1}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+(\frac{x}{x+1}\frac{1}{x+2}...\frac{n-2}{n-1})+...)\)
后面的式子我们不知道要怎么化简？其实就等于\(\frac{1}{x}(\frac{1}{x+1}+\frac{x}{x+1})(\frac{1}{x+2}+\frac{x+1}{x+2})...=\frac{1}{x}\)
所以\(f[x]=f[x+1]*\frac{x-1}{x}+f[x+1]*\frac{1}{x}+\frac{1}{x}=f[x+1]+\frac{1}{x}\)。
二次的话其实也是差不多的。
但是这里的式子有变，即：\((\frac{x-1}{x}\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+2^2(\frac{1}{x}\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+2^2(\frac{x-1}{x}\frac{1}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+...\)
没连到的话还是\(ff[i]=ff[i+1]*\frac{x-1}{x}\)，因为没变。
连到的话就有意思了，我们需要把系数的\(x^2\)变成\((x+1)^2\)，根据二项式定理，再用分配律，我们可以得到以下的式子：
\(ff[i]=ff[i+1]*\frac{1}{x}+\frac{1}{x}(3(\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+5(\frac{1}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+5(\frac{x}{x+1}\frac{1}{x+2}...\frac{n-2}{n-1})+...)\)
我们可以再提一次变成：
\(ff[i]=ff[i+1]*\frac{1}{x}+\frac{1}{x}(2(\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+4(\frac{1}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+4(\frac{x}{x+1}\frac{1}{x+2}...\frac{n-2}{n-1})+...)+\frac{1}{x}((\frac{x}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+(\frac{1}{x+1}\frac{x+1}{x+2}...\frac{n-2}{n-1})+(\frac{x}{x+1}\frac{1}{x+2}...\frac{n-2}{n-1})+...)\)
\(=ff[i+1]*\frac{1}{x}+2f[i+1]*\frac{1}{x}+\frac{1}{x}\)
全部加起来便是答案。
于是我们再次满心欢喜的一交：
- WA
- WA
- WA
- WA
- WA
- WA
- WA
- WA
- WA
- .W
太真实啦！！！
仔细检查发现，第\(1\)个点不会连出去！！！！
但是不慌，我们只需要再把\(ff[1]\)的期望的系数从\(x^2\)下调至\((x-1)^2\)就行了。
根据二项式定理，我们只需要\(ff[1]=ff[1]-2f[1]+1\)就行了。
应该是蓝题吧。
不难。
//一开始我的代码打了个特判，交了AC了之后才发现判错了，哈哈。，也就是说那个是不用判的，也就是n=1的情况。
#include<cstdio>
#include<cstring>
#define N 1100000
using namespace std;
double a[N],b[N];
int n;
int main()
{
scanf("%d",&n);
a[n]=1;b[n]=1;
for(int i=n-1;i>=1;i--)a[i]=a[i+1]+1.0/i/*(i+1-1)*/,b[i]=b[i+1]+(2*a[i+1]+1)*(1.0/i);
b[1]=(b[1]-2*a[1]+1);
double ans=0;
for(int i=1;i<=n;i++)ans+=b[i];
printf("%.10lf",ans);
return 0;
}
小结
我还是太弱了QAQ。