金华集训Day1——宇_weihongyu_2023的博客-程序员宅基地

技术标签: 未完成  by why  集训总结  

前言

说 好 的 第 一 天 数 论 呢 ? 哪 来 的 概 率 与 期 望 ! 说好的第一天数论呢?哪来的概率与期望!

概率与期望

1.概念随机变量:有多种可能的取值的变量

P ( A ) P(A) P(A):事件 A A A发生的概率
E ( X ) E(X) E(X):随机变量 X X X的期望值, E ( X ) = ∑ i = 1 ∞ P ( X = = i ) ∗ i E(X)=\sum_{i=1}^∞P(X==i)*i E(X)=i=1P(X==i)i
独立事件:互相不影响的事件

2.公式

①无穷次方公式

对于 0 &lt; x &lt; 1 0&lt;x&lt;1 0<x<1,由于 ∑ i = 0 n x i = 1 − x n + 1 1 − x \sum_{i=0}^nx^i=\frac{1-x^{n+1}}{1-x} i=0nxi=1x1xn+1,有 ∑ i = 0 ∞ x i = 1 1 − x \sum_{i=0}^∞x^i=\frac{1}{1-x} i=0xi=1x1

②概率积公式

P ( A ∗ B ) = P ( A ) ∗ P ( B ) P(A*B)=P(A)*P(B) P(AB)=P(A)P(B)
推导如下:
P ( A ∗ B ) = ∑ i ∑ j ( A = = i   &amp; &amp;   B = = j ) ∗ i ∗ j P(A*B)=\sum_i\sum_j(A==i\ \&amp;\&amp;\ B==j)*i*j P(AB)=ij(A==i && B==j)ij
                  = ∑ i ∑ j ( A = = i ) ∗ i ∗ ( B = = j ) ∗ j \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_i\sum_j(A==i)*i*(B==j)*j                  =ij(A==i)i(B==j)j
                  = ∑ i ( A = = i ) ∗ i ∗ ∑ j ( B = = j ) ∗ j \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_i(A==i)*i*\sum_j(B==j)*j                  =i(A==i)ij(B==j)j
                  = P ( A ) ∗ P ( B ) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =P(A)*P(B)                  =P(A)P(B)

③概率和公式

P ( A + B ) = P ( A ) + P ( B ) P(A+B)=P(A)+P(B) P(A+B)=P(A)+P(B)
推导如下:
P ( A + B ) = ∑ i ∑ j ( A = = i   &amp; &amp;   B = = j ) ∗ ( i + j ) P(A+B)=\sum_i\sum_j(A==i\ \&amp;\&amp;\ B==j)*(i+j) P(A+B)=ij(A==i && B==j)(i+j)
                   = ∑ i ∑ j ( A = = i   &amp; &amp;   B = = j ) ∗ i + \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_i\sum_j(A==i\ \&amp;\&amp;\ B==j)*i+                   =ij(A==i && B==j)i+
                       ∑ i ∑ j ( A = = i   &amp; &amp;   B = = j ) ∗ j \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sum_i\sum_j(A==i\ \&amp;\&amp;\ B==j)*j                       ij(A==i && B==j)j
                   = P ( A ) + P ( B ) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =P(A)+P(B)                   =P(A)+P(B)

3.前缀和技巧

对于离散变量 X X X P ( X = = K ) = P ( X &lt; = K ) − P ( X &lt; = K − 1 ) P(X==K)=P(X&lt;=K)-P(X&lt;=K-1) P(X==K)=P(X<=K)P(X<=K1)
概率为 P P P的事件期望 1 P \frac{1}{P} P1次后发生

4.拿球问题

T1

箱⼦⾥有 n n n个球 1... n 1...n 1...n,你要从⾥⾯拿 m m m次球,拿了后放回,求取出的数字之和的期望

S = ∑ i = 1 n X i E ( S ) = E ( ∑ i = 1 n X i ) = ∑ i = 1 n E ( X i ) E ( X i ) = m n ∗ i E ( S ) = m n ∗ ( 1 + . . . + n ) = m n ∗ ( 1 + n ) ∗ n 2 = m ∗ ( n + 1 ) 2 S=\sum^n_{i=1}X_i\\ E(S)=E(\sum^n_{i=1}X_i)=\sum_{i=1}^nE(X_i)\\ E(X_i)=\frac m n*i\\ E(S)=\frac m n*(1+...+n)=\frac m n*\frac {(1+n)*n} 2=\frac {m*(n+1)} 2 S=i=1nXiE(S)=E(i=1nXi)=i=1nE(Xi)E(Xi)=nmiE(S)=nm(1+...+n)=nm2(1+n)n=2m(n+1)

T2

箱⼦⾥有 n n n个球 1... n 1...n 1...n,你要从⾥⾯拿 m m m次球,拿了后放回,求取出的数字之和的期望

S = ∑ i = 1 m X i E ( S ) = E ( ∑ i = 1 m X i ) = ∑ i = 1 m E ( X i ) E ( X i ) = ∑ i = 1 n 1 n ∗ i = 1 n ∗ ( 1 + n ) ∗ n 2 E ( S ) = m ∗ 1 n ∗ ( 1 + n ) ∗ n 2 = m ∗ ( n + 1 ) 2 S=\sum^m_{i=1}X_i\\ E(S)=E(\sum^m_{i=1}X_i)=\sum^m_{i=1}E(X_i)\\ E(X_i)=\sum^n_{i=1}\frac 1 n*i=\frac 1 n*\frac {(1+n)*n} 2\\ E(S)=m*\frac 1 n*\frac{(1+n)*n} 2=\frac{m*(n+1)} 2 S=i=1mXiE(S)=E(i=1mXi)=i=1mE(Xi)E(Xi)=i=1nn1i=n12(1+n)nE(S)=mn12(1+n)n=2m(n+1)

T3

箱⼦⾥有 n n n个球 1... n 1...n 1...n,你要从⾥⾯拿 m m m次球,拿了后以 p 1 p1 p1的概率放回,以 p 2 p2 p2的概率放回两个和这个相同的球,求取出的数字之和的期望

S = ∑ i = 1 n X i X i = Y i ∗ i T = ∑ i = 1 n Y i = m E ( T ) = ∑ i = 1 n E ( Y i ) = m E ( Y i ) = n m E ( S ) = ∑ i = 1 n E ( X i ) = ∑ i = 1 n E ( Y i ) ∗ i S=\sum^n_{i=1}X_i\\ X_i=Y_i*i\\ T=\sum^n_{i=1}Y_i=m\\ E(T)=\sum^n_{i=1}E(Y_i)=m\\ E(Y_i)=\frac n m\\ E(S)=\sum^n_{i=1}E(X_i)=\sum_{i=1}^nE(Yi)*i S=i=1nXiXi=YiiT=i=1nYi=mE(T)=i=1nE(Yi)=mE(Yi)=mnE(S)=i=1nE(Xi)=i=1nE(Yi)i

游走问题

T1

在⼀条 n n n个点的链上游⾛,求从⼀端⾛到另⼀端的概率

S = ∑ i = 1 n − 1 X i E ( S ) = E ( ∑ i = 1 n − 1 X i ) = ∑ i = 1 n − 1 E ( X i ) E ( X i ) = E ( X i − 1 ) + 2 E ( S ) = ( n − 1 ) 2 S=\sum^{n-1}_{i=1}X_i\\ E(S)=E(\sum_{i=1}^{n-1}X_i)=\sum^{n-1}_{i=1}E(X_i)\\ E(X_i)=E(X_{i-1})+2\\ E(S)=(n-1)^2 S=i=1n1XiE(S)=E(i=1n1Xi)=i=1n1E(Xi)E(Xi)=E(Xi1)+2E(S)=(n1)2

T2

在⼀张 n n n个点的完全图上游走,求从⼀个点走到另⼀个点的概率

期望步数为n-1

T3

在⼀张 2 n 2n 2n个点的完全二分图上游走,求从⼀个点走到另⼀个点的概率

A = 1 + B B = 1 n ∗ 1 + n − 1 n ∗ ( A + 1 ) A=1+B\\ B=\frac 1 n * 1 + \frac {n-1} n *(A+1) A=1+BB=n11+nn1(A+1)

T4

在⼀张 n n n个点的菊花图上游⾛,求从⼀个点⾛到另⼀个点的概率

B = 1 A = B + C = 1 + C C = 1 n − 1 ∗ 1 + n − 2 n − 2 ∗ ( A + 1 ) B=1\\ A=B+C=1+C\\ C=\frac 1 {n-1} * 1+\frac {n-2} {n-2} *(A+1) B=1A=B+C=1+CC=n111+n2n2(A+1)

T5

在⼀棵 n n n个点的树上游⾛,求从根⾛到 x x x的期望步数

f [ i ] = 1 d [ i ] ∗ 1 + ∑ y 属 于 i 的 儿 子 ∗ 1 d [ i ] ∗ ( 1 + f [ y ] + f [ x ] ) E ( S ) = ∑ y 属 于 根 节 点 到 x 的 路 径 上 f [ y ] f[i]=\frac 1 {d[i]} *1+\sum_{y属于i的儿子}*\frac 1 {d[i]}*(1+f[y]+f[x])\\ E(S)=\sum_{y属于根节点到x的路径上}f[y] f[i]=d[i]11+yid[i]1(1+f[y]+f[x])E(S)=yxf[y]

T6

构造⼀张 200 200 200个点的⽆向图,使得上⾯从 S S S⾛到 T T T的随机游⾛期望步数

$$

$$

经典问题

T1

每次随机⼀个 [ 1 , n ] [1,n] [1,n]的整数,问期望⼏次能凑⻬所有数

T2

随机⼀个⻓度为 n n n个排列 p p p,求 p [ 1 … i ] p[1…i] p[1i] p [ i ] p[i] p[i]是最⼤的数的概率

T3

问满⾜上⾯那个题的 i i i的个数的平⽅的期望

T4

随机⼀个⻓度为 n n n的排列 p p p,求 i i i j j j的后⾯的概率

T5

随机⼀个⻓度为 n n n的排列 p p p,求它包含 w [ 1 … m ] w[1…m] w[1m]作为⼦序列/连续⼦序列的概率

T6

n n n堆⽯头,第 i i i堆个数为 a [ i ] a[i] a[i],每次随机选⼀个⽯头然后把那⼀整堆都扔了,求第 1 1 1堆⽯头期望第⼏次被扔

T7

随机⼀个⻓度为 n n n 01 01 01串,每个位置是 1 1 1的概率是 p p p,定义 X X X是每段连续的 1 1 1的⻓度的平⽅之和,求 E [ X ] E[X] E[X]

T8

给⼀个序列,每次随机删除⼀个元素,问 i i i j j j在过程中相邻的概率

T9

给定⼀棵树,将他的边随机⼀个顺序后依次插⼊,求 u , v u,v u,v期望什么时候连通

T10

1... n 1...n 1...n 这 n 个数,每次随机选择⼀个还在的数并且删掉他的所有约数,求期望⼏次删完

期望线性性练习题

T1

给定 n n n个硬币,第 i i i个硬币的价值为 w [ i ] w[i] w[i],每次随机取⾛⼀个硬币,获得的
收益是左右两个硬币的价值的乘积,求期望总价值

T2

N N N个数 a [ 1 … N ] a[1…N] a[1N],每次等概率选出两个数,然后合并成⼀个新的数放回来,得到的收益是新的数的值,求总收益的期望

T3

给定⼀个数列 W [ 1... N ] W[1...N] W[1...N],随机⼀个排列 H H H,如果 H [ i ] H[i] H[i] H [ i − 1 ] H[i-1] H[i1] H [ i + 1 ] H[i+1] H[i+1]都⼤,就获得 W [ I ] W[I] W[I]的收益,求期望收益

T4

给出⼀棵树,⼀开始每个点都是⽩的,每次选⼀个⽩点将他⼦树⾥所有点染⿊,求期望⼏次染⿊整个

T5

N N N个⿊球, M M M个⽩球,每次等概率取出⼀个球(不放回),将取出来的球的颜⾊写成⼀个 01 01 01序列,求 ” 01 ” ”01” 01

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weihongyu_2023/article/details/97617887

智能推荐

随便推点