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