CF1342F
很巧妙的一个计数题。
原题目等价于构建一个递增序列 \(p\)，赋予每个数字一个属性 \(b\)，满足 \(b_{p_i}=p_i\)，其余任选。且 \(\forall j,\sum\limits_{i=1}^n [b_i=p_j]a_i<\sum\limits_{i=1}^n [b_i=p_{j+1}]a_i\)。最大化递增序列 \(p\) 的长度。
先考虑一个朴素 dp，设 \(f(S,i,j,k)\) 表示已经把 \(S\) 集合中的数填上了 \(b\)，考虑当前填到了 \(p_i\)，\(p_i\) 填 \(j\)，\(\sum\limits_{p=1}^n [b_p=j]a_p=k\) 所能划分出的最多集合数，复杂度高到了天上去。
考虑优化这个 dp，上来发现 \(i\) 没有用，状态变为 \(f(S,i,j)\) ，含义为把 \(S\) 集合中的数填上了 \(b\)，考虑当前填到的 \(p\) 是 \(i\)，\(\sum\limits_{p=1}^n [b_p=i]a_p=j\) 所能划分出的最多集合数。注意到现在的瓶颈在于我们把值域塞进了状态。我们考虑进一步从这个方面入手。
一个常见的 trick 是把值域和状态互换，考虑这样做的可行性。显然如果 \(f(S,i,j)<f(S,i,k)\land j>k\)，则 \(f(S,i,j)\) 无用。也就是说，我们可以把状态 \(f(S,i,j)\) 转化为 \(g(S,i,f(S,i,j))\) 而转去做 \(j\) 的最小值。重新明确一下状态，\(f(S,i,j)\) 表示把 \(S\) 集合中的数填上了 \(b\)，考虑当前填到的 \(p\) 是 \(i\)，当前划分了 \(j\) 个集合，\(\sum\limits_{p=1}^n [b_p=i]a_p\) 的最小值。
考虑转移。每次去划分一个集合，设当前状态为 \(f(S,i,j)\)，枚举 \(S\) 的补集的子集 \(T\)，满足 \(\exists p\in T,p\ge i\)，且 \(\sum\limits_{i\in T} a_i\ge f(S,i,j)\)。令 \(p_0\) 为满足条件一的 \(p\) 的最小值，则有转移 \(f(S,i,j)\rightarrow f(S\cup T,p_0,j+1)\)，\(f(S\cup T,p_0,j+1)\) 对 \(\sum\limits_{i\in T}a_i\) 取最小值。时间复杂度 \(O(3^n n^2)\)。
CF1392H
期望好题！
下文中我们称鬼牌为 joker。
首先注意到每轮抽到 joker 后的局面都是一样的，因此不妨先考虑每两张 joker 之间的答案是期望是多少，那么大概有如下式子：
\[E=\sum_{i=1}^{n+1} i\frac{m}{n+m-i}\prod_{j=1}^{i-1}\frac{n-j+1}{n+m-j+1} \]注意到后面那一堆显然有递推关系，令 \(g_i=\prod\limits_{j=1}^{i}\frac{n-j+1}{n+m-j+1}\)，那么我们有 \(g_{i+1}=\frac{n-i}{n+m-i}g_i\)，此时上式写成了下面的形式：
\[E=\sum_{i=1}^{n+1} i\frac{m}{n+m-i}g_{i-1} \]可以线性计算。
接下来考虑期望抽的轮数。 注意到牌和牌之间是无标号等价的，那么设 \(f_i\) 表示当前剩下了 \(i\) 张牌没有抽到的期望轮数。注意到一个很重要的事情，一张抽到过的牌是没有用的，因此我们不妨直接看做不放回抽卡！
那么此时可以写出转移式，\(f_i=\frac{m}{m+i} (f_i+1)+\frac{i}{m+i}f_{i-1}\)。移项变形后可得 \(f_i=f_{i-1}+\frac{m}{i}\)。更近一步得到 \(f_n=f_1+\sum\limits_{i=2}^n\frac{m}{i}\)，\(f_1=\frac{m+i}{i}\)。
所以答案即为 \(f_nE\)。
看了一眼题解区发现对于 \(E\) 有更简洁的形式，但是要换一种思考方式或者大力变换。在这里只介绍前者。考虑对于每一轮，他的抽牌是把所有牌抽出来，然后算出前面没有 joker 的牌的数量。那么每张牌对答案的贡献为 \(\frac{1}{m+1}\)。根据期望的线性性，答案为 \(\frac{n}{m+1}+1\)。感觉也很厉害了。
CF1616H
超级计数好题，主打的就是一个敢设状态。
首先看到两两异或建出 01-trie 套路变成按位考虑，下文设 \(l(i)\) 表示 \(i\) 的左子树，\(r(i)\) 表示 \(i\) 的右子树。
尝试一个 dp，设 \(f_i\) 表示以 \(i\) 为根的子树的答案，那么对于一个位置 \(i\)，若 \(x\) 的第 \(i\) 位为 \(0\)，我们有转移 \(f_i=f_{l(i)}+f_{r(i)}\)。但是 \(x\) 为 \(1\) 就似了，因为这不是个子问题。
怎么办？考虑能不能继续往状态里扔垃圾。我们再加一个点，\(f_{i,j}\) 表示考虑在 \(i,j\) 的子树中选若干个数的答案，那么还是首先考虑边界，如果当前到达叶节点，有 \(f_{i,j}=2^{siz_i+[i\neq j]siz_j}\)，其中 \(siz_i\) 表示 \(i\) 的子树中点的数量。
现在考虑转移，对于当前的位置 \(dep\)，我们考虑如下转移：
-
\(x\) 的第 \(dep\) 为 \(0\)。
-
\(i=j\)。
这个时候只能选一侧子树，然后合并答案，有 \(f_{i,j}=f_{l(i),l(i)}+f_{r(i),r(i)}-1\)。
-
\(i\neq j\)。
此时对于每颗子树的子树内任选，对于两颗子树之间，一定只能是 \(l(i)\) 配对 \(r(i)\) 或 \(l(j)\) 配对 \(r(j)\)，转移即 \(f_{i,j}=(2^{siz(l(i))}-1)(2^{siz(r(i))}-1)+(2^{siz(l(j))}-1)(2^{siz(r(j))}-1)+f_{l(i),l(j)}+f_{r(i),r(j)}-1\)。
-
-
\(x\) 的第 \(dep\) 为 \(1\)。
-
\(i=j\)。
此时子树内任选，有 \(f_{i,j}=f_{l(i),r(i)}\)。
-
\(i\neq j\)。
此时可以随便选，有 \(f_{i,j}=f_{l(i),r(j)}f_{r(i),l(j)}\)。
-
注意要考虑一些空集的边界情况。
CF1503E
一道比较平凡的计数，感觉比上面的简单啊为啥 3100。
看到这种奇怪的计数一般考虑转化充要条件。一个首先的观察是，每一行黄色的连通块必须接 \(1\) 或 \(n\)，每一列蓝色的连通块必须接 \(1\) 或 \(m\)，否则直接不合法。进一步的观察，发现黄色和蓝色都要是单峰的，否则也直接不合法。再进一步，发现两个峰必须紧邻。
不妨假设现在黄色围成了两个连通块，然后现在我们去枚举两个峰的位置，有一个直观的理解是，从四个角走到峰，把路径和 \(x=1\) 的直线围成的封闭多边形染黄，然后转成对路径计数，这个东西是平凡的网格图路径数计数，式子大概是下面的形式：
\[2\sum\limits_{k=1}^{m-1}\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n \binom{i+k-1}{k}\binom{n-i+k-1}{k-1}\binom{n-j+m-k}{m-k}\binom{j+m-k-2}{m-k-1} \]蓝色同理。现在我们得到了一个 \(O(n^3)\) 的做法。但是注意到后面的若干项要么只与 \(i,k\) 有关，要么只与 \(j,k\) 有关，那么我们套路交换枚举顺序然后前缀和一下即可做到 \(O(n^2)\)。
注意两个都有两个峰的时候可能会算重，要容斥一下，具体来说是做第二遍的时候强制两个峰不交于一点。
CF1608F
首先考虑 dp 的状态应该有什么，那么显而易见的是要把位置 \(i\) 和当前 \(mex\) 扔进去，然后转移需要知道大于 \(mex\) 的数有啥，但是直接这样做是指数级的。
怎么做？我们考虑把贡献放到 \(mex\) 更改的时候去算。那么我们现在有状态 \(f(i,j,k)\) 表示当前考虑到了第 \(i\) 位，当前的 \(mex\) 为 \(j\)，前面一共有 \(k\) 个大于 \(mex\) 的数的方案数。转移时枚举第 \(i+1\) 个填什么，分三类讨论：
- \(a_{i+1}<j\)，\(f(i+1,j,k)\leftarrow f(i,j,k)\times j\)。
- \(a_{i+1}>j\)，\(f(i+1,j,k+1)\leftarrow f(i,j,k)\)。
- \(a_{i+1}=j\)，枚举 \(j'\) 与 \(k'\)，\(f(i+1,j',k')\leftarrow f(i,j,k)\times coef\)，其中 \(coef\) 是一个经典的组合问题，把 \(k-k'\) 个球放进 \(j-j'\) 个空盒子，每个盒子至少有一个球的方案数。注意这里还需要一个组合数 \(\binom{j}{j'}\) 表示从 \(j\) 个位置中选出 \(j-j'\) 个。
这样做的话复杂度 \(O(n^3k^2)\)，难以优化。
怎么办？考虑改变状态，重设 \(f(i,j,k)\) 表示当前考虑到了第 \(i\) 位，当前的 \(mex\) 为 \(j\)，前面一共有 \(k\) 种大于 \(mex\) 的数的方案数。此时继续按照上面分类讨论。
- \(a_{i+1}<j\)，\(f(i+1,j,k)\leftarrow f(i,j,k)\times j\)。
- \(a_{i+1}>j\)，此时考虑 \(a_{i+1}\) 是否出现过。
- 出现过，\(f(i+1,j,k)\leftarrow f(i,j,k)\times k\)。
- 没出现过，\(f(i+1,j,k+1)\leftarrow f(i,j,k)\)。
- \(a_{i+1}=j\)，枚举 \(k'\)，那么有 \(k-k'\) 个数对 \(j\) 产生影响。枚举新的 \(mex\)，有转移 \(f(i,j+k-k'+1,k')\leftarrow f(i,j,k)\times\frac{k!}{k'!}\)。
注意到上面的转移是一个类似于斜对角线转移的东西，那么我们可以去考虑一种前缀和优化，将后两维的加和作为第二维，我们惊奇的发现此时后面的可以做前缀和优化，最后转移过去时除掉系数 \(k'!\) 即可。
时间复杂度 \(O(n^2k)\)。
标签：frac,limits,siz,sum,计数,题目,考虑,合集,mex From： https://www.cnblogs.com/-Complex-/p/17573512.html