【Messages】 定义X=∑inxiX=\sum_{i}^nx_iX=∑in​xi​为读到需要的信息的学生的数量，其中xix_ixi​为第iii个学生是否读到自己需要的信息，如果读到就为111，否则为000。 根据期望的可加性可知: E(X)=E(x1)+E(x2)+..+E(xn)\mathbb{E}(X)=\mathbb{E}(x_1)+\mathbb{E}(x_2)+..+\mathbb{E}(x_n)E(X)=E(x1​)+E(x2​)+..+E(xn​) 对于每一个E(xi)\mathbb{E}(x_i)E(xi​)来说： E(xi)=1⋅P(第i个学生读到mi)+0⋅P(第i个...

【Checkpoints】 定义E(i)\mathbb{E}(i)E(i)为从第iii关开始到通关，所需要通过的关卡的期望。 假设从第 lll 关开始到第 rrr 关只有第 lll 关有存档点，那么： E(l)=12(E(l)+E(l+1))+1E(l+1)=12(E(l)+E(l+2))+1⋯E(r−1)=12(E(l)+E(r))+1\begin{matrix} \mathbb{E}(l)&=&\frac{1}{2}(\mathbb{E}(l) +\mathbb{E}(l+1)) + 1\\ \\ \mathbb{E}(l+1)&=&\frac{1}{2}(...

【Fork in the Road】 定义dp(i)dp(i)dp(i)为从房间iii到结束的期望。 先不考虑删边的情况，状态转移： {dp(u)=∑u→v1Graph[u].size⋅(dp(v)+1),u≠ndp(u)=0,u=n\begin{cases} dp(u)=\sum_{u\rightarrow v} \frac{1}{Graph[u].size}\cdot(dp(v)+1), & u\neq n \\ \\ dp(u)=0, & u= n \end{cases}⎩⎪⎨⎪⎧​dp(u)=∑u→v​Graph[u].size1​⋅(dp(v)+1),dp(u)=0,...

【New Year and Arbitrary Arrangement】 定义dp(i,j)dp(i,j)dp(i,j)为子序列"ab"的个数为iii且存在jjj个"a"时的期望。 状态转移为： dp(i,j)=PaPa+Pbdp(i,j+1)+PbPa+Pbdp(i+j,j)dp(i,j)=\frac{P_a}{P_a+P_b}dp(i,j+1)+\frac{P_b}{P_a+P_b}dp(i+j,j)dp(i,j)=Pa​+Pb​Pa​​dp(i,j+1)+Pa​+Pb​Pb​​dp(i+j,j) 特殊的，当i=0,j=0i=0, j=0i=0,j=0时： dp(0,0)=PaPa+Pbd...

【Little Pony and Expected Maximum】 定义P(Y=y)P(Y=y)P(Y=y)为投nnn次，得到最大点数为yyy的概率，但是这个值直接计算比较难。 可以先定义P(Y≤y)P(Y\le y)P(Y≤y)为最大点数小于yyy的概率，则P(Y=y)=P(Y≤y)−P(Y≤y−1)P(Y=y)=P(Y\le y)-P(Y\le y-1)P(Y=y)=P(Y≤y)−P(Y≤y−1) P(Y≤y)=P(x1≤y,x2≤y,...,xn≤y)=P(X≤y)n=(ym)n\begin{matrix} P(Y\le y)&=&P(x_1\le y,x_2\le y...

【increment of coins】 定义dp(i,j,k)dp(i,j,k)dp(i,j,k)为背包中分别有iii枚金币，jjj枚银币，kkk枚铜币时，操作次数的期望。 末态为已经存在某一种硬币有100枚，即 dp(100,i,j)=dp(i,100,j)=dp(i,j,100)=0;dp(100,i,j) = dp(i,100,j) = dp(i,j,100) = 0;dp(100,i,j)=dp(i,100,j)=dp(i,j,100)=0; 状态转移方程为: dp(i,j,k)=1.0+i×dp(i+1,j,k)+j×dp(i,j+1,k)+k×dp(i,j,k+1)i+j+kdp...

【擅长解密的小红同学】 设密码有NNN中可能，那么每次猜中的概率为: P=1NP=\frac{1}{N}P=N1​ 那么，猜了kkk次猜中的概率为: P(X=k)=(1−P)k−1PP(X=k)=(1-P)^{k-1}PP(X=k)=(1−P)k−1P，即前k−1k-1k−1次都没猜中，而第kkk次猜中。 则，期望为: E[X]=∑k≥1k⋅P(X=k)=∑k≥1k⋅(1−P)k−1P\mathbb{E}[X]=\sum_{k\ge 1}k\cdot P(X=k)=\sum_{k\ge 1}k\cdot (1-P)^{k-1}PE[X]=k≥1∑​k⋅P(X=k)=k≥1∑​k⋅(1−P)k−...

【GCD Table】 若选中的起始位置为(i,j)(i,j)(i,j)​，则： <mstyle displaystyle="false" scriptlevel="0">{<mstyle displaystyle="false" scriptlevel="0">gcd(i,j))</mstyle><mstyle displaystyle="false" scriptlevel="0">=</mstyle><m...

【Power Tower】 m→φ(m)→φ(φ(m))→...→1m\rightarrow \varphi(m) \rightarrow \varphi(\varphi(m)) \rightarrow...\rightarrow1m→φ(m)→φ(φ(m))→...→1 ，这个步骤最多会进行log⁡m\log mlogm次。 对于每次的查询区间[l,r][l,r][l,r]，最多计算log⁡m\log mlogm次，总的复杂度就是O(qlog⁡m)O(q\log m)O(qlogm)。 计算幂的时候要用到欧拉降幂。 #include <bits/stdc++.h> #define...

【Notepad】 欧拉降幂裸题。 所有nnn位bbb进制的数有bnb^nbn个，含前导000的数有bn−1b^{n-1}bn−1个，总共需要记录的数有bn−bn−1=(b−1)bn−1b^n-b^{n-1}=(b-1)b^{n-1}bn−bn−1=(b−1)bn−1​个，直接对ccc​取模。 当取模结果为000时，最后一页记录的数字是ccc个，需要特判一下。 #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10; int power(int a, ...

【Biorhythms】 当三重峰值出现时，一定满足x=p+23t1=e+28t2=i+33t3x=p+23t_1=e+28t_2=i+33t_3x=p+23t1​=e+28t2​=i+33t3​​​，可以列出同余方程为 {x≡p(mod  23)x≡e(mod  28)x≡i(mod  33)\left\{\begin{matrix} x\equiv p(\mod 23) \\ x\equiv e(\mod 28) \\ x\equiv i(\mod 33) \end{matrix}\right.⎩⎨⎧​x≡p(mod23)x≡e(mod28)x≡i(mod33)​ 直接套excrt，求...

【扩展中国剩余定理】 直接套excrt的板子。 #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10; int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int nx, ny; int d = exgcd(b, a % b, nx, ny); x = ny; ...

【Alternating Sum】 由上图可知，可以将求和式∑i=0nsian−ibi\sum_{i=0}^ns_ia^{n-i}b^i∑i=0n​si​an−ibi分成cnt=(n+1)/kcnt=(n+1)/kcnt=(n+1)/k个小段，每一段内的求和值为t[i]=t[i−1]×a−kbk,t[1]=∑i=0k−1sian−ibit[i]=t[i-1]\times a^{-k}b^k,t[1]=\sum_{i=0}^{k-1}s_ia^{n-i}b^it[i]=t[i−1]×a−kbk,t[1]=∑i=0k−1​si​an−ibi，可以用等比数列前nnn项和的公式求出，公比为a−kbk...

【乘法逆元】 方法1：线性求逆元，详细方式推导可以参考oi-wiki https://oi-wiki.org/math/number-theory/inverse/#_5 #include <bits/stdc++.h> #define int long long using namespace std; const int N = 3e6 + 10; int n, p, inv[N]; signed main() { cin >> n >> p; inv[1] = 1; for (int i = 2; i <= n; i+...