计数与概率期望小结

好久没写过总结了，感觉有的东西不写一写很容易忘，还是写一点东西。

计数

组合数

BZOJ4870 [SHOI2017] 组合数问题

题意

给定四个整数 (n,p,k,r) ，求 (displaystylesum_{i = 0}^{infty} inom{nk}{ik+r} mod p) 。

(1 le n le 10^9,0 le r < k le 50,2 le p le 2^{30} - 1) 。

技巧：考虑组合数的意义，转化问题。

题解

考虑上面的组合数的意义，我们可以将题目转化为，我们要在 (nk) 个物品中，选出 (mod p = r) 个物品的方案数。这个东西可以直接DP，然后矩阵乘法加速即可。

UOJ275 [清华集训2016] 组合数问题

题意

小葱想知道如果给定 (n,m) 和 (k)，对于所有的 (0 le i le n,0 le j le min(i,m)) 有多少对 ((i,j)) 满足 (inom{i}{j}) 是 (k) 的倍数。

答案对 (10^9+7) 取模。

(1 le n,m le 10^{18},1 le t,k le 100)，且 (k) 是一个质数。

技巧：利用卢卡斯定理对于条件转化

题解

首先由卢卡斯定理，原题的限制可以转化为，求数对 ((i,j)) 满足 ((i,j)) 在 (k) 进制下，必定存在某一位，满足 (i) 在这一为比 (j) 小，且 (i le n,j le min(i,m)) 。这个证明很简单，直接用卢卡斯定理，一直迭代下去就可以了。

接下来用一个数位DP做一下就可以了。记 (dp[i][0/1][0/1][0/1][0/1]) 表示当前填到了第 (i) 位，第一个数是否达到上界，第二个数是否达到 (m) 的上界，第二个数是否达到 (i) 的上界，是否存在某一位满足第一个数的某一位小于第二个数。注意第二个数的两个上界是要分开记的，否则转移的时候会转移串。这个自己写的时候会发现这个问题。转移枚举两个数下一位分别是什么即可。

UOJ300 [CTSC2017] 吉夫特

题意

给定一个长度为 (n) 的数列 (a_i) ，求有多少个长度不小于 (2) 的子序列 (a_{b_1},a_{b_2},cdots,a_{b_k})，满足 (displaystyleprod_{i = 2}^{k} inom{a_{b_{i - 1}}}{a_{b_i}} mod 2 > 0) 。

(1 le n le 211985,a_i le 233333) ，(a_i) 互不相同。

技巧：卢卡斯定理转化条件，利用分块思想平摊掉修改与查询的复杂度。

题解

首先，和上一题一样，利用卢卡斯定理转化条件，可以得到，我们只要求有多少长度不小与 (2) 的子序列 (a_{b_1},a_{b_2},cdots,a_{b_k}) ，满足后一个数是前一个数的子集。

不难想到记 (dp[i][S]) 表示到第 (i) 个数，当前最靠后的数为 (S) 的方案。直接的话，由于 (a_i) 互不相同，复杂度是 (3^{18}) ，不足以通过此题。

我们考虑我们转移的时候，如果我们记的 (S) 是上面这种，那么每次修改是 (O(1)) ，查询的时候复杂度最坏是 (2^{18}) ；如果我们记的 (dp[i][S]) 是所有 (S) 的子集的方案，那么我们每次修改的时候，复杂度最坏是 (2^{18}) ，但是查询是 (O(1)) 的。我们考虑平摊一下复杂度，即我们即 (dp[i][S1][S2]) 表示到第 (i) 个数，最后一个数前 (9) 位为 (S1) ，后 (9) 位为 (S2) 或者 (S2) 的子集的方案数。这样相当于把修改和查询最坏复杂度都降到了 (O(2^9)) ，总时间复杂度即为 (O(6^9)) 。

其他

课件里还讲了如何 (O(sqrt{n}log n)) 求组合数，不过分块打标更加优秀，也就没啥意义了。

组合计数

AGC001E BBQ HARD

题意

有 (n) 组烧烤材料，每组有 (a_i) 片牛肉和 (b_i) 片青椒。需要从中选择两组材料，并把材料串在一起排列，问有多少种排列方案。两种方案不同，当且仅当选择的材料不一样，或者排列的方式不一样。

(n le 200000,a_i,b_i le 2000) 。

技巧：组合意义的转化

题解

考虑把题目转化为，二维平面内有 (2n) 个点。每组材料对应点 ((-a_i,-b_i)) 和点 ((a_i,b_i)) 。接下来方案数就是所有第三象限的点走到第一象限的方案数之和，减去自己走到自己的方案数。

AGC002F Leftmost Ball

题意

有 (n) 种颜色的球，编号为 (1) 至 (n) ，每种有 (k) 个。将这 (nk) 个球排成一排，将每种颜色从左至右第一个球染成颜色 (0) 。求最后能得到多少种不同的序列。

(1 le n,k le 2000) 。

技巧：计数限制条件的转化

题解

由题目的限制，可以发现一个这样的性质，从左到右第 (i) 个 (0) 的左边最多出现了 (i - 1) 种颜色。然后每次填的时候会有两种决策，一种是加入一个新的颜色，另一种是加一个 (0) 。由于每种颜色个数还有限制，直接顺次填还是不方便，因此可以一次填上所有一种颜色，这个可以直接用组合数计算。然后就可以记 (dp_{i,j}) 表示确定了 (i) 个 (0) 和 (j) 种颜色的方案数，转移比较显然了。

简单计数

题意

(n) 个([1,m]) 内的变量，其中 (i) 不能连续出现超过 (a_i) 次，求方案数。

(1 le a_i le n le 5000,1 le m le 10^5) 。

技巧：简化相同转移降低复杂度

题解

首先不难想到一个 (dp) 。设 (dp[i][j]) 表示前 (i) 个数，最后一个数为 (j) 的方案数。容易写出一个简单的 (dp) 。

[dp[i][j] = sum_{k=1}^{m}dp[i-1][ k] - sum_{k=1}^{m}[k ot= j] dp[i-a_i-1][k] ]

直接转移是 (O(nm)) 的，需要优化。注意到对于 (a_i) 相同的数，(dp) 值是相同的，因此可以一起转移。复杂度优化为 (O(n^2 + m)) 。

FFT辅助计数

简单树题

题意

给定一个 (n) 个点的树，对于每一个 (1 le k le n) ，求有多少个 (k) 个点的集合可以用至多一条路径覆盖。

(1 le n le 10^5)

技巧：点分治+FFT的树上计数的套路

题解

如果我们将一个合法的点集记在满足条件的长度最小的链上，那么我们的计数会更加方便。考虑树上一条长度为 (i) 的路径，由于我们把贡献记在了长度最小的路径上，因此我们必须强制选择路径两端的点，那么我们记在这条路径上的方案数就是组合数的形式 。因此我们只要统计对于所有的 (i) ，长度为 (i) 的路径条数。这个问题可以用经典的点分治+FFT实现。

生成函数

生成函数最基本的用法，辅助计数

BZOJ3771 Triple

题意

有若干个互不相同的正整数 (a_i) ，从中选出至多三个，求选出的数的和为每种情况的方案数。

(a_i le 40000)。

技巧：生成函数的基本运用

题解

算是生成函数中比较简单的题目了。我们可以直接构造普通型生成函数，然后容斥掉重复取同一个的贡献就可以了。

此外，生成函数还可以用来优化一些递推式的计算。

举个很简单的例子，我们构造一个斐波那契数列的生成函数为 (F(x) = displaystylesum_{i = 0}^{infty}fib_nx^n) ，由于 (fib_i = fib_{i - 1} + fib_{i - 2},f_0 = f_1 = 1) ，所以 (F(x) = F(x)x + F(x)x^2 + 1) 。于是 (F(x) = frac{1}{1 - x - x^2}) 。于是可以用多项式求逆，解出 (F(x)) 。

注意，写生成函数的时候一定不要忘了边界项！

虽然这个问题直接递推更快，但对于某些问题，就必须利用到生成函数了，比如下面这道题，也是这类问题的一个模板题。

CF438E The Child and Binary Tree

题意

给出一个正整数集合 (c_i) ，对于所有 (1 le i le m) 求出有多少形态不同的二叉树点权均属于这个集合且点权和为 (i) 。

(1 le m,c_i le 10^5) 。

技巧：生成函数解决递推式的问题。

题解

我们设 (f(i)) 表示二叉树点权和为 (i) 的方案数，(a(x)) 表示是否存在 (c_i = x) 。所以我们会有 (f(0) = 1,f(i) = displaystylesum_{x,y}f(x)f(y)a(i-x-y)) 。

如果我们用 (F(x)) 表示 (f(i)) 的生成函数，(A(x)) 表示 (a(i)) 的生成函数，那么我们会有：

[egin{aligned} F(x) &= F(x)^2A(x) + 1 \ Leftrightarrow F(x) &= frac{1 pm sqrt{1 - 4A(x)}}{2A(x)} end{aligned} ]

然后这个求逆的地方，由于 (A(x)) 没有常数项，直接求逆会凉掉，因此得转化一下。

[F(x) = frac{2}{1 pm sqrt{1 - 4A(x)}} ]

然后求逆的时候用那个常数项非 (0) 的解去求即可。

这里多啰嗦一句多项式开方，其实也很简单，同样是利用倍增+FFT去求。假设我们已经求出了在模 (x^n) 的意义下，(A(x)) 的平方根 (B'(x)) ，我们要求 (A(x)) 在模 (x^{2n}) 的意义下，(A(x)) 的根式 (B(x)) 。于是我们会有

[B^2(x)-2B(x)B'(x)+B'^2(x)equiv 0pmod {x^{2n}} ]

解得

[B(x)=frac{A(x)+B'^2(x)}{2B'(x)} ]

于是求逆一下就可以了。

第一类斯特林数

第一类斯特林数 (S_1(n,m)) 表示把 (n) 个元素排成 (k) 个环的方案数，于是我们可以直接得到：

[S_1(n,k) = S_1(n - 1,k - 1) + (n - 1)S_1(n -1,k) ]

第一类斯特林数的生成函数可以用这个东西表示：

[sum_{i = 0} ^ {n}S_1(n,i) x^i = prod_{i = 0}^{n - 1}(x + i) ]

这个生成函数可以直接利用之前的递推式直接得到。由于 (S_1(n,i)) 对应的生成函数的项的次数为 (i) ，我们可以对着递推式理解一下。当我们给这个生成函数乘上一个新的项 ((x + i)) 的时候，如果我们在这里选择乘上 (x) ，相当于给我们的多项式次数 (+1) ，对应递推式中 (S_1(n - 1,k - 1) ightarrow S_1(n,k)) ，如果我们在这里选择乘上 (i) ，相当于多项式的次数不变，但是乘上了一个 (i) 的系数，对应递推式中 ((n - 1)S_1(n - 1,k) ightarrow S_1(n,k)) 。

这样的话，第一类斯特林数就可以用分治+FFT在 (O(n log ^ 2 n)) 的时间内求出来了。但是这还不够优秀。利用倍增+FFT，我们可以把复杂度优化到 (O(n log n))。

具体来说，令 (displaystyle F_n(x) = prod_{i = 0}^{n - 1}(x + i))，那么 (F_{2n}(x) = F_n(x) F_n(x + n)) 。而

[egin{aligned} F_n(x+n) &= sum_{i = 0}^{n - 1}S_1(n,i)(x+n)^i \&= sum_{i = 0}^{n - 1}S_1(n,i)sum_{j=0}^i inom{i}{j}x^jn^{i-j} \&= sum_{j = 0}^{n - 1}x^j sum_{i=j}^{n - 1} inom{i}{j}S_1(n,i)n^{i-j} end{aligned} ]

把式子拆开，就可以发现这是一个卷积形式。于是我们可以用倍增+FFT在 (O(nlog n)) 的时间内求解。

此外还有一个定义叫有符号第一类斯特林数，它的值就是在 (S(n,k)) 的基础上乘上一个 ((-1)^{n-k}) 。它的生成函数为

[sum_{i = 0} ^ {n}S_1(n,i) x^i = prod_{i = 0}^{n - 1}(x - i) ]

第一类斯特林数和上升下降幂还有这样的转化：

[egin{aligned} x^{overline{n}} &= sum_{i = 0}^{n}S_1(n,i)x^i \ x^{underline{n}} &= sum_{i = 0}^{n}S_1(n,i)(-1)^{n - i}x^i end{aligned} ]

其中 (x^{underline{i}}) 与 (x^{overline{i}}) 分别表示 (x) 的 (i) 次下降幂与上升幂。

第二类斯特林数

第二类斯特林数 (S_2(n,m)) 表示把 (n) 个元素分成 (k) 个非空集合的方案数，于是我们可以直接得到：

[S_2(n,k) = S_2(n - 1,k - 1) + kS_2(n -1,k) ]

利用容斥原理，我们可以得到第二类斯特林数的另外一个求法：

[S_2(n,m)=frac{1}{m!}sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n ]

这里的容斥利用的是，枚举有几个集合是空的。注意到每个集合都是一样的，所以最后答案要除一个 (m!)。利用NTT可以直接在 (O(nlog n)) 的时间内求出答案。

第二类斯特林数和上升下降幂还有这样的转化：

[egin{aligned} x^n &= sum_{i = 0}^{n}S_2(n,i)x^{underline{i}} \ &= sum_{i = 0}^{n}S_2(n,i)(-1)^{n - i}x^{overline{i}} end{aligned} ]

其中 (x^{underline{i}}) 与 (x^{overline{i}}) 分别表示 (x) 的 (i) 次下降幂与上升幂。

CF932E Team Work

题意

求 (displaystylesum_{i=0}^{n}C(n,i) imes i^k) 的值。

(1 leq n leq 10^9,1 leq k leq 5 imes 10^3) 。

技巧：斯特林数的经典转化

题解

利用普通幂与下降幂在第二类斯特林数的转化，我们可以得到：

[egin{aligned} sum_{i=0}^{n}C(n,i) imes i^k &= sum_{i=0}^{n}inom{n}{i}sum_{j=0}^{k}S_2(k,j)inom{i}{j}j! \ &= sum_{i=0}^{n}sum_{j=0}^{k}S_2(k,j) inom{i}{j} inom{n}{i}j! \ &= n!sum_{i=0}^{n}sum_{j=0}^{k}S(k,j) frac{1}{(n-i)!} frac{1}{(i-j)!} \ &= n!sum_{i=0}^{n}sum_{j=0}^{k}S_2(k,j) inom{n-j}{n-i} frac{1}{(n-j)!} \ &= n!sum_{j=0}^{k}S_2(k,j)sum_{i=0}^{n}inom{n-j}{n-i} frac{1}{(n-j)!} \ &= n!sum_{j=0}^{k}S_2(k,j) 2^{n-j} frac{1}{(n-j)!} \ &= sum_{j=0}^{k}S_2(k,j) 2^{n-j} n^{underline{j}} end{aligned} ]

于是就做完了，问题的关键一步在于幂次与下降幂的转化。

容斥原理

ARC093F Dark Horse

题意

有 (2^n) 名选手，编号为 (1) 至 (2^n) 。现在这 (2^n) 名选手将进行 (n) 轮淘汰赛，决出胜者。若 (x < y) ，则 (x) 能够战胜 (y) 。但有 (m) 个例外，(1) 号选手会输给这 (m) 个选手。问有多少中排列方式使得 (1) 号选手取得胜利。

(n,m le 16) 。

技巧：容斥之后，利用DP来加速求解

题解

为了方便，定义这 (m) 个人组成的集合为集合 (A) 。容易发现，与 (1) 号选手交战的选手，对应了 (n) 个区间内的编号最小值。如果只算某一个区间中集合 (A) 有人晋级的方案数，可能会有算重的情况。所以可以想到一个容斥，即计算满足集合 (S) 所包含的所有区间中，集合 (A) 有人晋级的方案数。最后容斥一下。

这个东西还是不大好算，于是考虑使用DP计数。设 (dp_{i,j}) 表示选出了集合 (A) 中前 (i) 大的选手，且集合 (S) 中所包含的区间均有集合 (A) 中的人晋级的方案数。转移还是比较显然的。

Upd : 这写的什么玩意儿……看这里

CF995F Cowmpany Cowmpensation

题意

给出一棵 (n) 个点的有根树，每个点可以有一个 ([1,d]) 内的整数边权，问有多少种点权满足儿子权值不大于父亲。

(1 le n le 3000,1 le D le 10^9) 。

技巧：利用容斥降低DP的复杂度

题解

容易想到枚举这棵树内一共出现了多少种数字，然后用组合数去计算最后的答案。但是直接DP的话，合并的时候你需要枚举重复的数字，复杂度相当高，需要简化一下问题。

考虑容斥，将恰好 (j) 种数字转化为至多 (j) 种数字。设 (dp_{i,j}) 表示以 (i) 为子树，至多出现了 (j) 种数字的方案数。转移的时候记一个前缀和就可以做到 (O(n^2)) 的复杂度。

概率与期望

题目我做了一些删减，过水太难的就删掉了……

普通期望题

概率与期望题，首先记住：概率顺推，期望倒推。因为期望顺推的话，你还需要多求一个概率。在不好求概率的时候倒推期望是最合适的。

CF605E Intergalaxy Trips

题意

有 (n) 个点，每天 (i) 号点到 (j) 号点的有向道路有 (p_{i,j}) 的概率开放。每天可以走一条开放的道路或者留在原地，求从 (1) 号点走到 (n) 号点最优的期望时间。注意，你的策略可以随着道路的开放与否做出改变。

(1 le n le 1000)。

技巧：期望倒推的利用，与贪心的结合

题解

我们设 (f(x)) 表示从 (x) 节点到 (n) 节点最优时间的期望，那么我们的最优策略肯定是，在所有你能到的节点中，走向期望时间最短的点。如果这个点的期望时间大于本身，那么就留在这个点，等待下一次。

那么我们可以考虑按照期望的大小从小到大确定每个点的答案。每次从所有未确定的点中，选择一个当前期望值最小的点。由于我们不会走向期望时间比自己大的点，因此，这样做是正确的。我们设 (a_i) 表示 (f(x)) 第 (i) 小的点的编号，那么我们有：

[f(a_i) = 1 + sum_{j = 1}^{i}f(a_j) P_{a_i,a_j}prod_{k = 1}^{j - 1}(1 - p_{a_i,a_k}) ]

这里在确定一个点之后，对于每个未确定的点维护一下新的答案，就可以在 (O(n^2)) 的时间内解决了。

BZOJ5058 期望逆序对

题意

给定一个 (1) 到 (n) 的排列，求 (k) 次随机交换之后，期望逆序对的数量。

(n le 500000,k le 10^9) 。

技巧：考虑某一对或某个物品对于答案的贡献；考虑末状态的期望

题解

考虑每对数字对答案的贡献。每对数字 (a_i,a_j) 在末状态的时候，所处位置有三种可能的情况，位于 (i) ，位于 (j) ，位于其他的位置。注意到在这里，每个点位于其他位置的概率是均等的。因此 ((i,j)) 这个数对的位置情况可以归为 (7) 种。把这 (7) 种情况的转移写成一个矩阵，就可以求出每种位置情况的概率。

直接对于每一个数对统计答案的话，时间复杂度仍然是 (O(n^2)) 的，于是我们要用一个BIT来统计贡献。这玩意儿有点难写，具体实现还是看代码比较好……

CF838D Airplane Arrangements

题意

有 (n) 个人排成一排，有 (m) 个人依次进场选位置。每个人开始会选择一个方向（从左至右或从右至左）并选择一个位置。他会走到他选择的那个位置，如果那个位置被人占用了，他会沿着他选择的方向一路走到第一个空位并坐下。求有多少种情况满足每个人都有座位。

(1 le m le n le 10^6) 。

技巧：巧妙的建模，找到概率相同的量

题解

把所有位置看成一个 (n + 1) 个点的环。其中第 (n + 1) 个点是一个特殊点，如果有人占据了这个点，那么意味着有人没有座位。如果我们假设这 (m) 个人可能以 (n + 1) 号点为起点，这显然不会影响合法的答案。但是这样修改了一下之后，每个人坐在每个位置上的概率是均等的。所以答案就是 (frac{n + 1 - m}{n + 1}(2n+2)^m)。

树上高斯消元解决树上期望问题

这种题主要还是要熟悉一下套路，一般来讲，可以把 (dp) 的式子写成 (f(x) = A_xf(fa[x]) + B_x)。然后从下到上一路推到根，就可以求出整棵树的 (dp) 值。

LOJ2542 随机游走

题意

给定一棵 (n) 个结点的树，你从点 (x) 出发，每次等概率随机选择一条与所在点相邻的边走过去。

有 (Q) 次询问，每次询问给定一个集合 (S)，求如果从 (x) 出发一直随机游走，直到点集 (S) 中所有点都至少经过一次的话，期望游走几步。

特别地，点 (x) 视为一开始就被经过了一次。

(1 le n le 18,1 le Q le 5000) 。

技巧：树上高斯消元；MinMax容斥

题解

题意等价于，给定一个点集，求经过这个点集里的点的时间的Max的期望。Max的期望可以说相当不好求，这里考虑利用MinMax容斥，将时间Max的期望转化为时间Min的期望。MinMax容斥的式子大概长这样：

[displaystyle max{S}=sum_{Tsubseteq S}(-1)^{|T|-1}min{T} ]

证明大概可以这样考虑。设 (max{S} = x)，将除了 ({x}) 与 (varnothing) 之外，将所有集合两两配对。配对方式就是将一个不含 (x) 的集合和这个集合加上 (x) 这个元素形成的集合配对。这样两个集合的最小值肯定是相等的，会相互抵消。最后剩下的集合中，空集没有最小值，故答案即为 (x) 。

MinMax容斥之后，我们就只要求第一次经过某个点集的期望时间了。设 (f(x,S)) 表示从 (x) 出发，第一次经过集合 (S) 中的点的期望时间。这个东西可以分两类讨论：

若 (x in S) ，则 (f(x) = 0)；

若 (x otin S) ，则(displaystyle f(x)=[f(fa[x])+1+sum (f(ch[x])+1)] imes frac{1}{deg[x]})。

利用树上高斯消元，将 (f(x)) 表示为 (A(x)f(fa[x]) + B(x)) 的形式。于是我们有

[displaystyle (1-frac{sum A_v}{deg[u]}) f(u) = frac{1}{deg[u]}f(mathrm{fa}[u])+(1+frac{sum B_v}{deg[u]}) ]

把左边除过去，然后就可以得到答案了。

似乎这个复杂度并不是出题人给出的正解？但是还是能跑得过。

Trip

题意

给定一棵 (n) 个点，以 (1) 号点为根的树，每个点为黑色或白色。从 (1) 号点出发，每次随机走向一个相邻的节点。如果该点为黑色或第一次经过该点，则计数器加 (1) 。如果走到叶子节点整个过程将结束。求计数器的值的期望。

(n le 10^6) 。

技巧：树上高斯消元，期望综合难题；大胆设出未知数。

题解

首先考虑只有黑点的时候，该怎么做。黑点是经过一次就算一次贡献，如果我们设 (f(x)) 表示从 (x) 出发，经过的黑点的期望个数，那么我们就可以得到一个DP方程

[f_i = [i is black] + [deg[i] > 1]frac{sum f(j)}{deg[i]} ]

其中 (j) 为所有与 (i) 相邻的点。那么这里直接用树上高斯消元即可解决。

接下来考虑只有白点的情况。由于白点只在第一次经过的时候做出贡献，那么我们只需求出经过白点的概率 (g_i) 。由于当我们从 (1) 号点出发的时候，想要经过 (i) ，必须经过 (fa_i) 。我们设 (h_i) 为从 (fa_i) 走到 (i) 节点的概率，那么我们有 (g_i = g_{fa_i} imes h_i) 。

考虑我们该如何求 (h) 。设 (a_i) 表示从 (i) 走到 (fa_i) 的概率，那么我们有这样一个式子：

[h_i = frac{1}{deg_{fa_i}}(1 + h_ih_{fa_i} + sum a_jh_i) ]

其中 (j) 是 (i) 的儿子节点。

解释一下这个式子。第一项表示我第一步就到了 (i) 节点；第二项表示我第一步走到了父亲节点，那么我为了走到 (i) 节点，就要往下走两步，概率分别为 (h_{fa_i}) 与 (h_i) 。第三项表示我第一步走到了其他的儿子节点，那么我需要先往上走一步，再往下走一步。

为了求 (h) 我们还得求 (a) 。不过所幸 (a) 求起来是很简单的。容易发现这样一个式子：

[a_i = frac{1}{deg_i}(1+sum a_ja_i) ]

同样 (j) 为 (i) 的儿子节点。这个式子理解起来很简单。第一项就是一步走对，第二项就是往下走了，然后要往上走两步。

以上的 (h) 和 (a) 均用树上高斯消元都可以求出来，于是问题终于解决啦！