持续更新。。。
有些内容因为机房电脑死机而丢失，这里标记为 TODO
根式指数和
Statement
求
\[ 2^m\sum_{\sum c_i=n,c_i\ge 0}\dfrac{(2n)!}{\prod(2c_i)!}\prod_{i=1}^ma_i^{c_i} \]（若 \(n\bmod 2=1\)，答案为 \(0\)；否则上式中的 \(n\) 为实际输入的 \(n/2\)）
给出了 \(n(\le10^9),m(\le 7),a_i\)
Solution
DP：
\(f(i,S)\) 表示 \(n=i\)，\(a_i^{k_i}\) 的 \(k_i\) 的奇偶性：若 \(i\in S\)，\(k_i\) 为奇数，否则 \(k_i\) 为偶数；的答案
\[ f(i,S)=\sum_{i=1}^m\sqrt{a_i}\cdot f(i-1,S\oplus\{i\}) \]\(Ans=f(n,\varnothing)\)
考虑 \(\sqrt{a_i}\) 是个实数，不适合放到矩阵乘法中，优化一下式子：
\[ f(i,S)=\sum_{i=1}^m[i\in S?1:a_i]\cdot f(i-1,S\oplus\{i\}) \]感性理解，非常的对
于是矩阵乘法优化 DP，做完了！！！！！！！
宝石路线
Solution
设 \(f(t,u,S)\) 表示 \(1\to u\) 经过了 \(t\) 条边，收集到的宝石集合为 \(S\) 的方案数
设一条边 \((u,v,T)\) 表示 \(u\to v\) 的有向边，上面的宝石集合为 \(T\)
\(f(0,1,\varnothing)=1\)
\[ f(t,u,S)=\sum_{(v,u,T)\in E}\sum_{P\cup T=S}f(t-1,v,P) \]\(Ans=\sum_u f(T,u,\{1,2,3,4\})\)
考虑优化，一个 \((n\times 2^4)\times 1\) 的矩阵 \(A_{(u,S)}\) 表示 \(f(t,u,S)\)
\(A_{(1,\varnothing)}=1\)
\((n\times 2^4)\times(n\times 2^4)\) 的转移矩阵 \(B_{(v,P),(u,S)}=[\exists (v,u,T)\in E\land P\cup T=S]\)
\(Res\gets B^TA\)
\(Ans=\sum_{i}Res_{i,1}\)
时间 \((2^4n)^3\log T\)
Solution
列出限制条件：\(Ans=|有红\cap 有黄\cap 有蓝\cap 有绿|\)
这有点难求，直接转化：\(Ans=|U|-|无红\cup 无黄\cup 无蓝\cup 无绿|\)
考虑容斥，系数为 \((-1)^{限制条数}\)
问题变成形如：限定这个图中只能走某些“无红且无黄”的边，走到某个点的方案数
设可走的边集为 \(E'\)
设 \(f(t,u)\) 表示 \(1\to u\) 走 \(t\) 步的方案数
\[ f(t,u)=\sum_{(v,u)\in E'}f(t-1,v) \]\(f(0,1)=1\)
考虑矩乘优化：
\(A\) 为 \(n\times 1\) 的矩阵，初始 \(A_{1,1}=1\)
\(B\) 为 \(E'\) 邻接矩阵的转置
\(Res=B^TA\)（这个 \(T\) 是指 \(B\) 的 \(T\) 次方）
做完了，因为容斥要做 \(2^4\) 次这个问题，复杂度 \(O(2^4n^3\log T)\)
指数乘多项式形式2
Statement
\[ a_n=a_{n-1}+\sum_{i=1}^p\left(b_i^n\sum_{j=1}^{q_i}c_{i,j}n^j \right) \]\(n\le 10^9\)，\(\sum_{i=1}^p q_i\le 100\).
Solution
设 \(\displaystyle L=\max_{i=1}^pq_i\)
考虑 \(n\to n+1\)，我们的目标是维护每个 \(b_i^nn^j\)，考虑
\[ b_i^{n+1}(n+1)^j=\sum_{p=0}^jb_i^nn^p\cdot b_i\binom{j}{p} \]所以得出答案：
\[ \begin{bmatrix} 1&0&c_{1,1}&c_{1,2}&\cdots&c_{p,q_p}\\ 0&b_1\binom{0}{0}&0&0&\cdots&0\\ 0&b_1\binom{1}{0}&b_1\binom{1}{1}&0&\cdots&0\\ 0&b_1\binom{2}{0}&b_1\binom{2}{1}&b_1\binom{2}{2}&\cdots&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&0&\cdots&b_p\binom{q_p}{q_p} \end{bmatrix} \begin{bmatrix} a_{n-1}\\b_1^nn^0\\b_1^nn^1\\b_1^nn^2\\\vdots\\b_p^nn^{q_p}\\ \end{bmatrix}=\begin{bmatrix} a_n\\b_1^{n+1}(n+1)^0\\b_1^{n+1}(n+1)^1\\b_1^{n+1}(n+1)^2\\\vdots\\b_p^{n+1}(n+1)^{q_p}\\ \end{bmatrix} \]时间：\(O(n^3\log T)\)
路线方案数
Solution
设 \(f(t,u)\) 为 \(1\) 走 \(t\) 距离到 \(u\) 的方案数，\(f(0,1)=1\)
\[ f(t,u)=\sum_{(v,u,w)\in E}f(t-w,v) \]设 \(m=\max w\le 10\)
考虑优化，先设一个 \(nm\times 1\) 的矩阵 \(A\)，\(A_{(t,u),1}\) 表示 \(f(t,u)\)
再设一个 \(nm\times nm\) 的转移矩阵 \(B\)，对于前 \(m-1\) 个 \(t\)，\(B_{(t,u),(t+1,u)}=1\)，否则 \(B_{(t,u),(s,v)}=[\exists(v,u,w)\in E,s=t-w]\)
\(A\) 初始时 \(A_{(0,1),1}=1\)，\(0\) 为 \(A\) 中最大的 \(t\)
令 \(R=B^TA\)（这里 \(B^T\) 是指 \(B\) 的 \(T\) 次方）
\(R_{(T,u),1}\) 即为每个 \(u\) 的答案
时间：\(O((nm)^3\log T)\)，\(nm\le 100\)
生日悖论
Solution
考虑
\[ 1-\dfrac{\prod_{i=0}^{n-1}(365-i)}{365^n}\le50\% \]解得
\[ n\ge 23 \]前缀染黑期望步数
Solution
设 \(P(i)\) 表示染了 \(m\) 次后，恰好前 \(i\) 个格子被染黑的概率
\[ P(i)=\dfrac{i^m-(i-1)^m}{n^m} \]于是
\[ Ans=\sum_{i=1}^nP(i)i \]找回帽子问题
Solution
设 \(D(n)\) 为 \(n\) 错排数
\[ Ans=\dfrac{\binom{n}{k}D(n-k)}{n!} \]\(D(n)\) 有很多求法，举个例子，用容斥算：
\[ D(n)=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)!=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!} \]用递推算：
\[ D(n)=(n-1)(D(n-1)+D(n-2)) \]飞行棋问题
Solution
定义距离终点 \([0..d]\) 的位置区间为安全区。
这个游戏有两个阶段：
- 距离终点距离 \(>d\)，这时他会一直朝终点走
- 距离终点距离 \(\le d\)，这时他会一直在安全区内游走
考虑第一个阶段：
设 \(f(i,j)\) 为从距终点 \(i+d\) 的地方开始，花 \(j\) 步进入安全区的概率。
\[ f(i,j)=\dfrac1d\sum_{k=1}^d\begin{cases} f(i-k,j-1)&i>k\\ 1&i\le k \end{cases} \]考虑第二个阶段：
设 \(q\) 为两人都在安全区内，先手获胜的概率
\[ \begin{aligned} Q&=\dfrac{1}{d}+\left(1-\dfrac1d\right)^2\dfrac1d+\left(1-\dfrac{1}{d}\right)^4\dfrac1d+\cdots\\ &=\dfrac1d\dfrac{1-\left(1-\frac1d\right)^{2\infty}}{1-\left(1-\frac1d\right)^2}\\ &=\dfrac{1}{d-d(1-\frac1d)^2}\\ &=\dfrac{d}{2d-1} \end{aligned} \]考虑结合两个阶段，求出答案：
设 \(P(a,b)\) 为先手用 \(a\) 步进入安全区，后手用 \(b\) 步进入安全区，先手获胜的概率
\[ P(a,b)=\begin{cases} \left(1-\frac1d \right)^{a-b}q&a>b\\ 1-\left(1-\frac1d\right)^{b-a}+\left(1-\frac1d\right)^{b-a}q &a\le b \end{cases} \]那么
\[ Ans=\sum_{a}\sum_{b}f(x-d,y-d)P(a,b) \]考虑优化空间：滚动 \(f\) 的一维即可。
一无所有
Solution
先分别去除 \(A,B\) 中被严格偏序的无用点，然后分别按 \(x\) 排序
证明贡献满足四边形不等式：如下图
然后根据决策单调性，即可分治解决。
投币取石子问题
Solution
设 \(f(i,0/1)\) 为还有 \(i\) 颗石子，先手为 A/B 时 A 的获胜概率
则 \(f(0,0)=0,f(0,1)=1\)
若 \(f(i-1,0)>f(i-1,1)\)：
\[ \begin{aligned} f(i,0)&=(1-p)f(i-1,1)+p(1-q)f(i-1,0)+pq(1-p)f(i-1,1)+pqp(1-q)f(i-1,0)+\cdots\\ &=(1-p)f(i-1,1)\dfrac{1-(pq)^{\infty}}{1-pq}+p(1-q)f(i-1,0)\dfrac{1-(pq)^{\infty}}{1-pq}\\ &=\dfrac{(1-p)f(i-1,1)+p(1-q)f(i-1,0)}{1-pq}\\ f(i,1)&=(1-q)f(i-1,0)+q(1-p)f(i-1,1)+qp(1-q)f(i-1,0)+qpq(1-p)f(i-1,1)+\cdots\\ &=(1-q)f(i-1,0)\dfrac{1-(pq)^{\infty}}{1-pq}+q(1-p)f(i-1,1)\dfrac{1-(pq)^{\infty}}{1-pq}\\ &=\dfrac{(1-q)f(i-1,0)+q(1-p)f(i-1,1)}{1-pq} \end{aligned} \]若 \(f(i-1,0)\le f(i-1,1)\)，同理可得：
\[ \begin{aligned} f(i,0)&=\dfrac{pf(i-1,1)+(1-p)qf(i-1,0)}{1-(1-p)(1-q)}\\ f(i,1)&=\dfrac{qf(i-1,0)+(1-q)pf(i-1,1)}{1-(1-p)(1-q)} \end{aligned} \]答案：\(f(n,0)\)
无向图碰面期望步数
Solution
设 \(f(u,v)\) 为 \(A\) 在点 \(u\)，\(B\) 在点 \(v\) 的期望碰面次数，其中 \(u,v\) 连通
设 \(S(u)\) 为 \(u\) 以及与 \(u\) 相邻的所有点组成的集合，\(p(u,v)\) 为 \(S(v)\) 中距 \(u\) 最近的点中编号最小的一个.
\(f(i,i)=0\)
\[ f(u,v)=\dfrac{1}{|S(u)|}\sum_{k\in S(u)}\begin{cases} 1&k=p(k,v)\\ f(k,p(k,p(k,v)))&\text{otherwise}. \end{cases} \]不能 \(O(n^3)\) 直接消元，考虑如何没有后效性地转移.
注意到每过一个单位时间，\(A,B\) 的距离一定会减少，于是按 \(u,v\) 的距离从小到大转移即可
收集邮票
Statement
\(n\) 个数，每次等概率随机选一个数，设收集到所有数的时间为 \(t\)，求 \(E\left(\frac{t(t+1)}{2}\right)\)
Solution
设 \(s_i\) 表示目前已经有 \(i\) 种邮票，花多少步到达 \(n\)
\[ Ans=\dfrac{E(s_0^2)+E(s_0)}2 \]设 \(f(i)=E(s_i)\)
\[\begin{aligned} f(i)&=\dfrac in(f(i)+1)+\dfrac{n-i}n(f(i+1)+1)\\ f(i)&=f(i+1)+\dfrac n{n-i} \end{aligned} \]设 \(g(i)=E\left(s_i^2\right)\)
\[ \begin{aligned} g(i)&=\dfrac inE\left((s_i+1)^2 \right)+\dfrac{n-i}nE\left((s_{i+1}+1)^2 \right) \\ &=\dfrac in\left(g(i)+2f(i)+1 \right)+\dfrac{n-i}n\left(g(i+1)+2f(i+1)+1 \right)\\ g(i)&=g(i+1)+2f(i+1)+2\dfrac{i}{n-i}f(i)+\dfrac{n}{n-i} \end{aligned} \]\(f(n)=g(n)=0\)
更简单的方法：（sto sto sto sto sto 国队 orz orz orz orz orz）
设 \(f(i)\) 为 \(i\to i+1\) 期望花费多少
为了转移，还需要设 \(g(i)\) 为 \(0\to i\) 期望多少步、\(h(i)\) 为 \(i\to i+1\) 期望多少步
\[ f(i)=\dfrac in(f(i)+g(i+1))+\dfrac{n-i}ng(i+1) \]之类的式子，我也记不清楚了（应该是这个）
然后考虑 \(g(i)\) 里面每个 \(\dfrac ni\) 的贡献次数，即可得到最简式子。
弱题
Statement
\(M\) 个数，值域 \([1..N]\)，操作 \(K\) 次，每次选一个数 \(x\) 然后 \(x\gets x\bmod N+1\)，问最后 \(1\sim N\) 每个数的期望出现次数
\(N\le 10^3,M\le 10^9,K\le 2^{31}-1\)
Solution
朴素 DP：设 \(f(i,k)\) 为第 \(k\) 轮答案
\[ f(i,k)=\dfrac{n-1}{n}f(i,k-1)+\dfrac1nf(i-1,k-1) \]这里 \(i-1\) 值域在 \([1..N]\) 内
然后循环矩阵优化，\(O(n^2\log K)\)
所以为什么是卡特兰数？
Statement
\(\text{LIS}\le 2\) 的排列计数，\(n\le 2\cdot 10^6\).
Solution
根据 Dilworth 定理，条件等价于可以划分为最多两个下降子序列。
先考虑对于一个排列，如何计算他能被最少划分为多少个下降子序列：
设 \(d_i\) 为第 \(i\) 个下降子序列的末尾值，初始为 \(\inf\)，考虑贪心：
考虑加入一个数 \(x\)，取出所有末尾值中第一个 \(\ge x\) 的，然后修改为 \(x\).
原问题相当于只有 \(d_1,d_2\) 两个下降子序列，\(d_1<d_2\)
根据上述贪心，考虑 DP 算出原问题的答案：
设 \(f(i,j)\) 为已选前 \(i\) 个数，有 \(j\) 个小于 \(d_1\) 的未选数的方案数，有 \(i+j\le n\)
有两种转移：
- 下一个数接在 \(d_2\) 后面，该数一定为未选数的最大值
- 下一个数接在 \(d_1\) 后面，该数 \(<d_1\)
边界：\(f(0,n)=1\)
答案：\(f(n,0)\)
注意到 \(f(i)\) 为 \(f(i-1)\) 的前缀和，故容易转化为 \(g(i,j)=g(i-1,j)+g(i,j-1)\)
注意到其几何意义，就是从 \((0,n)\) 开始，每次往下或者往右移一步，不能越过 \(y=n-x\)，到达 \((n,0)\) 的方案数
所以他是卡特兰数。
翻硬币
Solution
手动消元！
\(f(i)\) 当前有 \(i\) 个正面朝上的硬币，到 \(n\) 个正面朝上的期望次数。
\(f(k)=0\)
\[ f(i)=\dfrac in(f(i-1)+1)+\dfrac{n-i}n(f(i+1)+1) \]然后手动消元。
咋校园呢：
\[\begin{aligned} f(n)&=0\\ f(n-1)&=\dfrac inf(n-2)+1\\ f(n-2)&=\dfrac inf(n-3)+\dfrac{n-i}nf(n-1)+1 \end{aligned} \]此时将 \(f(n-1)\) 代入 \(f(n-2)\) 的式子再化简，就变成了只与 \(f(n-3)\) 有关的一个式子
将 \(f(n-2)\) 类似地代入。。。。
\(f(0)\) 没有 \(f(-1)\)，也就是得到 \(f(0)\) 是某个数
然后再将 \(f(0)\) 反代入 \(f(1),f(2),\ldots\)
得出所有 \(f\)。
具体过程：
设 \(f(i)=A_if(i-1)+B_i\)
\(A_{n-1}=\dfrac{n-1}{n},B_{n-1}=1\)
\(A_{n-i}=\dfrac{n-i}{n-i\cdot A_{n-i+1}}\)
\(B_{n-i}=\dfrac{i\cdot B_{n-i+1}+n}{n-i\cdot A_{n-i+1}}\)
\(f(0)=B_0\)
然后反推回去
好麻烦呀！有没有更简单的方法呢？
一种更简单的方法：（sto sto sto sto 蝈対 orz orz orz orz）
设 \(f(i)\) 为从 \(i\to i+1\) 的期望步数
\[ f(i)=\dfrac{n-i}n+\dfrac in(1+f(i-1)+f(i)) \]解得
\[ f(i)=\dfrac n{n-i}+\dfrac i{n-i}f(i-1) \]做后缀和然后输出即可。
骰子棋2
Solution
国队：
方程直接列。
消元直接消。
设 \(f(i)\) 为 \(i\) 到 \(n\) 的期望步数。
\(f(n)=0\)
\[ f(i)=1+\dfrac16\sum_{v\in 投骰子能到的地点}\dfrac{1}{|\text{Card}(v)|}\sum_{Op\in\text{Card}(v)}\begin{cases} f(v+d)&Op=\text Md\\ f(v)+r&Op=\text Sr \end{cases} \]猴子大战
Solution
首先朴素 DP：
设 \(P(S)\) 为集合 \(S\) 的胜率，令 \(T=U-S\)
\[ P(S)=\dfrac{1}{|S|}\sum_{u\in S}\dfrac1{|T|}\sum_{v\in T}a_{u,v}P(S\cup\{v\})+a_{v,u}P(S-\{u\}) \]下面是一个本质相同的式子，没啥区别
\[ P(S)=\dfrac1{|S|(n-|S|)}\sum_{c=1}^nP(S\oplus\{c\})\begin{cases} \sum_{d\in S}a_{d,c}&c\not\in S\\ \sum_{d\not\in S}a_{d,c}&c\in S \end{cases} \]考虑这题咋做。
结论：\(P(S\cup T)=P(S)+P(T)\)
考虑 \(S,T,R\) 三人玩游戏，根据常识有 \(P(S)+P(T)+P(R)=1\)
考虑 \(S\cup T,R\) 两人玩游戏，根据常识有 \(P(S\cup T)+P(R)=1\)
所以 \(P(S)+P(T)=P(S\cup T)\)
于是只考虑所有单个牌的集合的胜率即可！
设 \(f(i)\) 为牌 \(i\) 的胜率，照着最上面的式子有
\[ \begin{aligned} f(i)&=\dfrac{1}{n-1}\sum_{j\not=i}a_{i,j}(f(i)+f(j))+a_{j,i}\cdot 0\\ &=\sum_{j\not= i}\dfrac{a_{i,j}}{n-1}f(i)+\dfrac{a_{i,j}}{n-1}f(j) \end{aligned} \]还有 \(\sum f(i)=1\)
高斯消元即可。
卡牌游戏
Solution
设 \(f(i,j)\) 为剩下 \(i\) 个人时，从庄家开始第 \(j\) 个人的存活概率
\[ f(i,j)=\dfrac1m\sum_{k=1}^m\begin{cases} f(i-1,j-a_k) &a_k<j\\ 0&a_k=j\\ f(i-1,j+i-a_k) &a_k>j \end{cases} \]\(f(1,1)=1\)
集邮问题2
Solution
设 \(f(S)\) 为当前有 \(S\) 集合的卡，到集齐所有卡还需要期望多少步。
\[ f(S)=1+\sum_{i=1}^n\begin{cases} p_if(S)&i\in S\\ p_if(S\cup\{i\})&i\not\in S \end{cases} \]化简得
\[ f(S)=\dfrac{\displaystyle 1+\sum_{i\notin S}p_if(S\cup\{i\})}{\displaystyle 1-\sum_{i\in S}p_i} \]设全集为 \(U\)，\(f(U)=0\)
答案为 \(f(\varnothing)\)
奖牌魔法
Solution
设 \(f(a,b,c)\) 为当前有 \(a\) 块铜牌 \(b\) 块银牌 \(c\) 块金牌，达到目标状态的期望耗费魔力数
\[ \begin{aligned} f(a,b,c)=\ &\dfrac{a}{a+b+c}(f(a-1,b+1,c)+x)+\\ &\dfrac{b}{a+b+c}(f(a,b-1,c+1)+y)+\\ &\dfrac{c}{a+b+c}f(a+1,b,c-1) \end{aligned} \]\(f(0,0,n)=0\)
因为 \(a+b+c=n\)，有效的状态数是 \(O(n^2)\) 的，所以直接高斯消元即可
我的电影
Statement
长度为 \(n\) 的序列，值域 \(1\sim m\)
定义一段区间的权值为，其所有仅出现过一次的数 \(x\) 的 \(w_x\) 之和
求最大权值
Solution
shaber题。
扫一遍
考虑加入一个数 \(x\)，设其上一次出现位置为 \(p\)，其上上次出现位置为 \(q\)
那么 \([q+1..p]\) 区间减 \(w_x\)，\([p+1..i]\) 区间加 \(w_x\)，每次查区间 \(\max\)
做完了。
这个 trick 是“区间本质不同子串数”的严格子集。
奇怪的植物
Solution
shaber题。
楼房重建
把 push_up 改成 O(log) 的就行了。
顺便学一下兔队线段树：
兔队线段树
一种维护前缀 \(\max\) 序列的方法。
本题是要求动态维护严格前缀 \(\max\) 序列的长度。
记 \(s_i\) 为 \(i\) 的斜率
一个节点 \([l,r]\) 维护：
- 本区间 \(s_i\) 的 \(\max\)
- 仅考虑这个区间时，前缀 \(\max\) 序列长度。也就是不考虑 \([1,l-1]\) 区间对本区间的影响。
第二个信息 push_up 时直接线段树二分，记 \(\text{calc}(u,x)\) 为 \(u\) 子树内，只考虑 \(>x\) 的数时的答案，有
def calc(u, x):
if u is a leaf node:
return [u.mx > x]
if u.ls.mx > x:
return calc(u.ls, x) + (u.ans - u.ls.ans)
else:
return 0 + calc(u.rs, x)
这题就做完了。
注意到上述 calc 利用了 ans 的可减性（u.ans - u.ls.ans），那么若 ans 没有可减性咋做捏？
仔细思考，把 ans 的定义改成“考虑该区间的影响后，右子树的答案”即可！
对于叶子，其 ans 视作未定义。
然后修改 calc 函数，只需要把 u.ans - u.ls.ans 改为 u.ans 即可。
最小差值序列
Slope Trick。当时学了一通。
TODO
凑整数
同余最短路 / 模意义下的完全背包的转圈做法 板子题。
单格染黑期望步数
Solution
设 \(f(i)\) 为从 \(i\) 个黑色格子到 \(i+1\) 个黑色格子的染色次数期望
\[ \begin{aligned} f(i)&=\dfrac in(1+f(i))+\dfrac{n-i}n\\ \Longrightarrow f(i)&=\dfrac n{n-i} \end{aligned} \]答案：\(\sum_{i=0}^{n-1} f(i)\)
标签：begin,end,dfrac,sum,Solution,一些,aligned From： https://www.cnblogs.com/laijinyi/p/18544620