2022 CCPC 广州站
L. Station of Fate【计数】
Description
有 n 个人，m 个站台，排成了 m 条队伍。
需要保证每条队伍至少有 1 个人，求总方案数。
两个方案不同需要至少满足下述一种情况：① 有站台的队伍所含的人不同 ② 人虽相同，但排队顺序不同。
Solution
考虑将 n 个人排成一列，在里面放 m-1 个隔板来分成 m 条队伍。
对于 n 个人的每一种排列都统计一次答案即可得所有方案。
\(mayb\) 想问题的时候可以倒着想？对于每一种不同的排队方案，将它们按照站台顺序排成一个序列，两两不同的方案一定要么最后的序列互不相同，要么是序列相同但是分割点不同。所以只需要讨论所有的序列和所有可能的分割就行。
H. GameX 【贪心】
Description
给定一个长度为 n 的自然数序列 S。
现在 Alice 和 Bob，每轮操作分别向序列中插入一个数。若 k 轮操作后，MEX(S) 是偶数，则 Alice赢；否则 Bob 赢。
说明：MEX(S) 指的是不在序列 S 中的最小自然数。
Solution
Alice每次向序列中插入最小的不在序列中的奇数，
Bob每次向序列中插入最小的不在序列中的偶数。
E. Elevator【二位数点/树状数组】
Description
有 n 个电梯，m 层楼。每秒，电梯上升 1 层。
在所有电梯开始运行前，可以在任意楼层（除 1 , m）按电梯。但是注意，一旦有电梯到达这个楼层，该电梯会停 1 秒，但是后面来的电梯都不会停了。若同时有多个电梯到达，则序号最小的作为第 1 个到达的。
给定所有电梯的出发时间，所有电梯都从第 1 层出发，求最少的按电梯次数使得第 \(i\) 个电梯第一个达到 \(m\) 层。
对于从 1 到 n 所有的 i，都输出一个答案。（若无答案则输出 -1）
Solution
首先注意到最多只能按 \(m-2\) 次电梯。
对于 \(i\)，答案分为序号比它小的部分和序号比它大的部分，
对于序号小于 \(i\) 的部分，答案为 \(\sum_{j=1}^{i-1}(x[j]\leq x[i])*(x[i]+1-x[j])\)；
对于序号大于 \(i\) 的部分，答案为 \(\sum_{j=i+1}^{n}(x[j] < x[i])*(x[i]-x[j])\)
考虑先求 \(\sum_{j=1}^{n}(x[j]< x[i])*(x[i]-x[j])\)，再求\(\sum_{j=1}^{i-1}(x[i]\leq x[j])*1\)。
前面一个式子非常好求，直接排序求个前缀和再处理下就能出来，重点是第二个式子怎么求。
注意到这是一个二维数点问题，求关键值1 和 关键值 2 都小于一个点的所有点。放到坐标系中理解，相当于求一个点左下角的所有点（满足横纵坐标均不大于该点）。
用树状数组求。按照\(x[i]\)为第一关键字，\(id\)为第二关键字的顺序从小到大将电梯加入树状数组，树状数组以 \(id\) 为下标。每次加入一个电梯前（后也行），统计一个\(sum(id-1)\)就是所求的值（第二个式子的值）了。
M. XOR Sum 【数位dp/计搜】
Description
一个长度为 \(k\) 的非负整数的序列 \(A\) 的 \(value\) 定义为： \(\sum_{i=1}^{k}\sum_{j=1}^{i-1}a_i\ XOR\ a_j\)
给定 \(A\) 的 \(value\) 为 \(n\)，限制\(0\leq a_i\leq m\)。
求满足以上条件的不同的序列 \(A\) 的个数。
Solution
将数二进制展开，按位考虑。
发现对于 \(2^p\) 位，对 \(value\) 的贡献为在该位上，01对的数目乘上 \(2^p\)，因为只有 \(0\ XOR\ 1 =1\)。
考虑从高位到低位枚举统计答案，需要注意的是由于有 \(m\) 的限制，所以我们还需要记录一个当前有多少个数卡在上限的参数。
\(dfs(digi,lim,res)\) 表示现在在\(2^{digi}\)位，有\(lim\)个数达到\(m\)的上限，还需要的\(value\)为 \(res\)。
若 \(m\) 在 \(digi\) 位上为 \(1\)，则可以从受限制的 \(lim\) 个数中选 \(i\) 个，剩下不受限制的 \(n-lim\) 个数中选 \(j\) 个，把选出来的 \(i+j\) 个数的这一位置为 \(1\)， 这样贡献的 \(value\) 为 \((i+j)*(k-i-j)\)，方案数为\(C_{lim}^i*C_{k-lim}^j*dfs(digi+1,i,res-val)\)；
若 \(m\) 在 \(digi\) 位上为 \(0\)，则只可以从不受限制的 \(n-lim\) 个数中选 \(j\) 个数，将此位置为 \(1\)，这样贡献的 \(value\) 为 \(j*(k-j)\)，方案数为\(C_{k-lim}^j*dfs(digi+1,lim,res-val)\)；
需要特别说明的是，由于需要记忆化，记录 \(res\) 有两种方法：① 开一个 \(map<pair<int,int>> f[][]\)，数组的下标为 \(digi\) 和 \(lim\)，\(map\) 的值的 \(first\) 对应 \(res\)，\(second\) 记录方案数；② 直接开三维数组，但是处理一下，只考虑不低于 \(digi\) 位的 \(res\)，这个\(res\) 是个相对值（比如说 \(res\) 原本应该是 \([1001011]_2\)，现在考虑到\(2^2\)，那么我们记录的 \(res\) 为\([10010]_2\) ，在搜索下一位时才加上后面的数位）。注意采用这种方法的话，贡献是不需要乘上 \(2^{digi}\) 的。
找点性质剪枝，注意到 \(k\) 个数能产生最大贡献为 \(\lfloor k/2\rfloor * \lceil k/2\rceil\)，若 \(\lfloor k/2\rfloor * \lceil k/2\rceil +\lfloor k/2\rfloor * \lceil k/2\rceil - 1<res\)，则最后一定是不合法的，可以直接剪掉。如何理解这一点：因为在当前位没有减去的 \(res\)，如果累计到下一位至少会是 \(res*2\) ，如果次位最少都会剩余 \(\lfloor k/2\rfloor * \lceil k/2\rceil\)，也就是单个位能产生的最大贡献，那么后面肯定不能将\(res\)全部消去。
由于 \(k\leq 18\)，所以\(res\leq 9*9*2=162\)。
则总的状态数为\((log_2 m) *k *162\)，最多为 \(40*18*162\)。但是注意到在搜索函数中枚举了 \(i,j\)，所以总的复杂度应该是\(40*9*9*162=524880\)。（应该是这样\(8\)，欢迎指正！！）
一定要注意考虑一些边界情况、特殊情况！比如 \(k=1、m=1、n=0\)。
关键代码见下，完整代码见\(Code\)板块。
ll m, n;
//m : 限制数列元素的范围不大于 m ；n：A的题目定义的val=n
//int dm[M]; //记录 m 的每一位是多少
int k, C[M][M]; //数列的长度; 组合数数组
int f[M][M][N]; //另一种方式，详见solution
int dfs(int digi, int lim, int res) {
//现在在2^digi位，有lim个数达到m的上限，高于等于这个位的还需要的value为 res
if (digi < 0) return res == 0;
if (res < 0) return 0;
if ((k / 2) * ((k + 1) / 2) * 2 - 1 < res) return 0; //k < 2 时，这个式子无法成立
if (f[digi][lim][res] != -1) return f[digi][lim][res];
int ret = 0;
int add_res = digi == 0 ? 0 : n >> (digi - 1) & 1;
if (m >> digi & 1) {
for (int i = 0;i <= lim;++i) //在受限制的数中选 i 个置为 1
for (int j = 0;j <= k - lim;++j) { //在不受限制的数中选 j 个置为 1
int val = (i + j) * (k - i - j); //这样选产生的贡献value
if (val > res) continue;
ret += 1ll * C[lim][i] * C[k - lim][j] % mod * dfs(digi - 1, i, (res - val) << 1 | add_res) % mod;
ret %= mod;
}
}
else {
for (int j = 0;j <= k - lim;++j) { //在不受限制的数中选 j 个置为 1
int val = j * (k - j); //这样选产生的贡献value
if (val > res) continue;
ret += 1ll * C[k - lim][j] * dfs(digi - 1, lim, (res - val) << 1 | add_res) % mod;
ret %= mod;
}
}
return f[digi][lim][res] = ret;
}
其他：用杨辉三角形预处理组合数！
I. Infection【树形dp/换根dp】
Description
有一种细菌正在感染一棵树的 \(n\) 个结点！
结点 \(i\) 成为整棵树第一个被感染的结点的概率为 \(\frac{a_i}{\sum_{j=1}^n a_j}\)；
若结点 \(i\) 有相邻的结点已经被感染，则它被感染的概率为 \(p_i\)。
求最后整棵树恰好有 \(k\) 个结点被感染的概率（mod），\(k\in[1,n]\)。