暑假二期总结
Grisses
·
·
个人记录
内容各种各样：排列组合，概率期望
一、排列组合
https://vjudge.net/contest/575025
1.情侣？给我烧了！
对于一个 k，设 g_x 是 x 对情侣不坐在一起的情况数，易得答案为 2^k\times A_n^k\times C_n^k\times g_{n-k}。
那么就是如何求 g。
\begin{array}{c}
g_x&=&4x(x-1)\left[g_{i-1}+2(x-1)g_{x-2}\right]
\end{array}
从两对情侣中选出两人，并讨论剩下两人是否在一起即可。
2.建设城市
对于一段长度为 n，值域大小为 m 的区间，单调的方案数为 C_{m+n-1}^{n-1}，即将其看作 n 个相同的球，m 个不同的盒子，可空的方案数。
然后如果 x 和 y 在同一侧，那么就将其间的所有楼看作一栋。
如果不在同一侧，枚举两栋楼的高度，将大区间拆成 4 段求值即可。
3.数学作业
观察题目，
发现对于异或而言二进制下每一位相对独立。
所以我们可以枚举集合内的元素的每一个二进制位，并计算它的贡献。
对于二进制下第 i 位，我们假设 n 个元素中有 a 个该位为 1，b 个该位为 0。易得 a+b=n。
- 如果 a=0，那么无论怎么选，这一位都不会产生贡献。即贡献为 0。
- 如果 a>0，那么假设第 pos 个元素二进制下该位为 1。那么对于剩下 n-1 种元素的 2^{n-1} 种选法，每种选法产生的贡献不为 0 就是 2^{i-1}，如果原来的贡献为 0，那我们选上第 pos 个元素，将贡献改为 2^{i-1}；如果本身有贡献，我们就不选第 pos 个元素，不变他。综合起来，总共献为 2^{i-1}\times2^{n-1}。
所以，我们将所有的元素全部或起来，最后乘上 2^n-1 即可
4.
首先，我们可以预处理出每一位前面的左括号个数以及后面的右括号个数，记为 l_i 和 r_i。
那么，我们枚举选的第一个右括号的位置 i，即枚举所有 s_i=')' 的 i，然后再枚举左右括号的个数 k，此时的方案数为 \sum\limits_{k=1}^{r_i}C_{l_i}^k\times C_{r_i-1}^{k-1}（实际上上界应该是 \min(l_i,r_i)，但是当 m>n 时，C_n^m=0，所以补上几项也无所谓）。
看着上面的式子，我们进行一些改造：
\begin{array}{c}
&\sum\limits_{k=1}^{r_i}C_{l_i}^k\times C_{r_i-1}^{k-1}\\
=&\sum\limits_{k=1}^{r_i}C_{l_i}^k\times C_{r_i-1}^{r_i-k}\\
=&C_{l_i+r_i-1}^{r_i}
\end{array}
其中最后一步由范德蒙德恒等式得出。
范德蒙德恒等式
\sum\limits_{i=0}^{n}C_n^i\times C_{m}^{r-i}=C_{n+m}^r
证明，假设我们要在 n+m 个球中选出 r 个，那么我们可以前 n 个球选 i 个，后 m 个球选 r-i 个，然后根据加乘原理将方案数算出，即是上式。
5.
如果我们现在已经放完了前 i-1 种球共 sum 个，方案数为 ans，而第 i 种球有 a 个。
那么，为了保证第 i 种球在前 i-1 种球放完后放完，我们第 i 种球种必有一个放在最后。
然后我们就只有 a-1 个球了，这些球可以在前面随便放，即放在前面 sum 个球分出的 sum+1 个间隙里，方案数为 C_{a+sum-1}^{sum}（类似盒球问题）。
所以现在的方案数为 ans\times C_{a+sum-1}^{sum}。
6.Count the Arrays
首先，我们从 m 个数中选出 n-1 个（有一对重复）。
然后我们在这 n-1 个数中选出重复的那个，但不能是最大值，所以 n-2 种方案。
最后我们枚举剩下的 n-3 个数是在最大值的左边还是右边，共 2^{n-3} 种方案。
所以，总方案数为 C_m^{n-1}\times (n-2)\times 2^{n-3}
7.New Year and Permutation
因为题目要求的是 n 的排列，所以符合条件的 l,r 一定是满足一段连续的长度为 r-l+1 的数在一起。
所以我们枚举这个长度。
对于长度为 len 的一串数，他们有 n-len+1 种选择。同时又有 n-len+1 个位置供他们选择。并且内部有 A_{len}^{len} 种排列方式。所以总共的方案数就是 (n-len+1)^2\times A_{len}^{len}。
答案就是对其累加求和。
8.Bus Number
发现长度只有 18，直接暴搜加上可重集排列。
可重集排列
若不同的数共有 n 种，第 i 种有 a_i 个。
则总排列数为 \dfrac{(\sum\limits_{i=1}^na_i)!}{\prod\limits_{i=1}^na_i!}。
显然是这样，总排列除去每种数内部重复的情况。
9.组合数问题
预处理每种阶乘的质因子数量，然后对于 C_n^m，按照其定义式判断是否每种质因子的数量都不小于 k 的数量，然后前缀和统计答案即可
10.虔诚的墓主人