牛客937992666号

分类

题解(76)

/ 注册

全部文章（共77篇）

题解 | 超多面骰子 #

一个拥有个面的骰子，期望投掷多少次才能保证每一面都至少出现过一次？设随机变量表示上述条件所需的投掷次数，求设：表示：现在已经有个面了，还需要期望投掷次会有个面表示：现在已经有个面了，还需要期望投掷次会有个面表示：现在已经有个面了，还需要期望投掷次会有个...

2026-01-17

0 40

题解 | 随机路径长度期望 #

给定一个有向无环图，个点，条边，可以存在重边。设为图中所有简单路径(允许长度为，即起点与终点相同)的集合。从集合中等概率随机选择一条路径并沿着它行走，定义一条路径的长度为其经过的边数即随机变量为所选路径的长度，计算的期望值对取模的结果，即显然是离散型随机变量：的取值可以为，...

2026-01-17

0 48

题解 | 抢红包 #

必须知道期望的公式，知道公式了就直接快速幂解决了设一个离散型随机变量的所有可能的取值为，这些取值对应的概率为，则，这个叫做离散型随机变量的均值或者数学期望(简称期望) 但题目连续性随机变量，那么所以第一个人：剩余金额为，获得红包的期望金额为所以第二个人：...

2026-01-17

0 39

题解 | [SDOI2008]仪仗队 #

从原点到点的这一条射线，如果，那么这条射线一定经过并且最先经过点题目的意思相当于从朝这范围里面发射无数条射线，求每条射线最先经过的点的个数范围是当或者时，只有一个点即或者当时也满足条件然后显然可以用欧拉函数直接得到，但是欧拉函数求的是有多少个与互质的数...

2026-01-17

0 34

题解 | 阶幂 #

给定，求例如时，即求这与上一道题洛谷P4139 上帝与集合的正确用法十分相似，但是仍有区别推一下这道题目的欧拉公式吧：定义所以求..... 可以写出大致的代码： #include<bits/stdc++.h> using na...

2026-01-17

0 37

题解 | 洛谷P4139 上帝与集合的正确用法 #

定义，可以证明，在某一项后都是同一个值，求这个值 .... 即求解 2 的无限次幂塔模 p，利用扩展欧拉定理递归简化幂运算，同时通过线性筛（欧拉筛）预处理欧拉函数...

2026-01-17

0 31

题解 | 【模板】扩展欧拉定理 #

给定三个正整数，，求，其中快速幂的时间复杂度为，最大为，；先不说可不可能超时的问题，这个数字得用字符串存储，所以快速幂并不能直接解决。正确的解法是使用扩展欧几里得定理欧几里得定理：如果整数与整数互质，则有，其中是欧拉函数，表示到与互质的数的个数 ...

2026-01-16

0 48

题解 | 【模板】扩展欧几里得算法求解乘法逆元 #

对于整数，若存在整数满足：，则称是在模意义下的乘法逆元，记为首先，求解乘法逆元的方法有两种：方法一：费马小定理使用该方法的前提是：必须是质数，并且与互质(不是的倍数) 费马小定理内容：如果是质数，那么对任意与互质的整数，有c成立那么，所以，即可用快速幂...

2026-01-16

0 46

题解 | 【模板】欧拉函数计算Ⅰ ‖ 朴素求值：试除法 #

欧拉函数表示中与互质的数的个数求：首先将经行质因数分解：，其中是不同的质因子那么与互质的数不能被整除，从到一共有个数，那么：第一步：减去能被单个质因子整除的数的个数能被整除的数有个，能被整除的数有个，...，能被整除的数有个所以第一步要减去第...

2026-01-16

0 30

题解 | 动态序列 #

给定长度为的数组，执行两种操作：求解整个序列的第小的值将这个位置上的元素修改为，即每次操作时，输入一个整数，如果，那么执行操作1；如果，则再输入一个整数，然后将的值修改为传统线段树是维护数组下标区间的信息，例如： ...

2026-01-15

0 27