• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[QBXT游记]Day3 Test & Day4

开发技术 开发技术 2周前 (05-04) 9次浏览

因为这里的内容比较混杂,所以先放个目录

目录
  • Day3 Test
    • T1
    • T2
    • T3
    • T4
  • Day4
    • 随机试验
      • 要求
      • 栗子 One
      • 概念
      • 事件运算
        • 包含
        • 相等
        • 互斥
        • 补集
        • 加法(和)
        • 减法(差)
        • 乘积
        • 运算律
    • 概率
      • 性质
      • 条件概率
    • 期望
      • 栗子 Two
        • Describe
      • 贝叶斯公式
    • 独立事件

Day3 Test

仍然是被小学时完虐了,这些笔记是比较草的,绝大部分都没有使用(LaTeX)

T1

实际上这个题没必要高精度

首先把x当作字符串读进来,然后算出长度,然后用ans作为答案

然后:

for(R LL i=1;i<=len;i++) ans=(ans*10+x[i]-'0')%y;
fw(ans);

T2

用f[i]代表把3*i的地点铺满的方案数

i=1时,只能放1×1的,每个都能染m种颜色,故为m3

i=2时,2m3+m6

f[i]=m3f[i-1]+2m3f[i-2]

实际上就是每次考虑最后一列:是去填充三个1×1的还是让后两行填2×2的

使用矩阵快速幂优化,结构体搞一个矩阵,然后进行优化

T3

很明显如果想拿正解的话不能把C(n,m)拿出来

利用费马小定理:xp 同余 x1 (mod p)

所以 xy 同余 xy%(p-1)(mod p)

算出C(n,m) % (p-1)=?就能知道指数

p-1=100003470=2x3x5x53x677x929

然后用卢卡斯定理去算一算,最后Crt合并

T4

a0=(x,y)

a1=(x,y+1)

a2=(x,y+2)

a n-1=(x,y+n-1)

x=lcm(a0,a1,a2,a3,…,a n-1)

y % a0 = 0

(y+1) % a1=1

y % a1 =-1

y % a1 =a1-1

y+2 % a2 =0

y % a2 =a2-2

y % a n-1=a n-1

Day4

随机试验

要求

  1. 不能预先确定结果

  2. 实验之前可以预测所有可能结果或范围

  3. 可以在相同条件下重复实验

栗子 One

扔骰子🎲,投针实验(づ ̄ 3 ̄)づ

概念

  1. 样本空间:随机试验所有可能结果组成的集合
  2. 离散样本空间:有限个选择的结果
  3. 无穷样本空间:顾名思义,无限个选择都结果
  4. 事件发生:在一次实验中……
  5. 必然事件:在扔骰子中,1 2 3 4 5 6,也就是说是样本空间全集
  6. 不可能事件:不会发生的事件,对应一个空集

事件运算

事件集合的运算和集合的运算大致相同

包含

和集合中的子集差不多

相等

两个事件的集合完全相同

互斥

对于两个集合没有任何交集

补集

和集合的补集运算一致,同样,需要定义一个全集

加法(和)

和集合中的将两个集合合并一样

减法(差)

如A={1,2,3},B={3,4,5}

那么A-B={1,2}

乘积

求2个集合的交集

运算律

  • 交换律:A并B=B并A,A交B=B交A
  • 结合律:A并(B并C)=(A并B)并C,交集同理
  • 分配律:不再写了,和上面的差不多
  • 对偶律:取(A交B)的补集=A的补集 并 B的补集,反之亦然

概率

定义参见Oi Wiki

事件A的概率称为P[A]

性质

  • (sum P[A]=1)
  • 事件之间没有交集,则概率可以相加
  • P(空集)=0
  • 若A1,A2,A3…,An互不相交,则P(A1∪A2∪A3…∪An)=P(A1)+P(A2)+…+P(An)
  • 如果A是B的子集,那么P(B-A)=P(B)-P(A)。对于一般的A和B,P(B-A)=P(B)-P(AB)
  • 对于所有A,满足0<=P(A)<=P(1)
  • P(A∪B)=P(A)+P(B)-P(AB)

条件概率

当一件事情已经发生的时候,另一件事情发生的概率

(P(A|B)=frac{P(AB)}{P(B)})

乘法法则:(P(AB)=P(A)cdot P(B|A)=P(B)cdot P(A|B))

期望

根据每一种情况的概率来求每一种情况的权值,然后把权值求和

如当投骰子的时候,求扔出来数的期望,这里的每一个数的权值就是这个数

栗子 Two

扔两次骰子x1和x2,求第一次扔出来的数和第二个扔出来的数的和的期望(E[x1+x2])

可以发现有36种情况,如果按照定义,应当把每一种情况的概率×权值然后在求和

但是这里引入一个比较重要的性质:期望的和=和的期望

所以(E[x1,x2]=E[x1]+E[x2])

如果是多个的话,前面是6n的复杂度,后者则是6n

Describe

箱子里有3个1和1个2,每次取一个数不放回

贝叶斯公式

(P(B_i|A)=frac{P(B_i)P(A|B_i)}{sumlimits_{j=1}^n P(B_j)P(A|B_j)})

当左边不能求的时候,可以把条件概率反转一下啊用右面求

独立事件

对于独立的A,B,P(B|A)=P(B)


程序员灯塔
转载请注明原文链接:[QBXT游记]Day3 Test & Day4
喜欢 (0)