当前位置：首页 > news >正文

两个常见的计数问题 trick

news 2025/9/17 11:30:10

两个非常有用的计数 trick，虽然感觉比较典。

计数转 01

有一件事情：\(v=\sum_{i=1}^V [v \geq i]\)，\(V\) 为值域。看着好像没有什么突破性的转变，但是当我们对很多东西进行统计的时候，如果对于 有多少个大于等于 某个值 \(v\) 是好做的话，那么我们就可以做这个转化：\(\sum v_i=\sum_{j=1}^V \sum [v_i \geq j]\)。

unknown

给定一个长度为 \(n\) 的 \(0\) 到 \(n-1\) 的排列 \(a\)，有 \(q\) 个询问，每次询问一个区间 \([l,r]\) 的所有子区间的 \(mex\) 之和，一个子区间的 \(mex\) 为区间内最小的未出现的非负整数。
\(n,q \leq 10^5\)。

我们先考虑转化计数的方法，对于 \(i=1,...,n\) 来看询问的区间内有多少个子区间满足 \(mex \geq i\)，至于为什么 \(i\) 只用枚举到 \(n\) 因为 \(a\) 的值域到 \(n-1\) 所以 \(mex\) 也就顶到 \(n\)。

怎么计数呢，既然 \(mex \geq i\)，显然有 \(0,1,2,...,i-1\) 的数全都有，如果我们记录了它们的位置，那么现在就是要看 \([l,r]\) 有多少个子区间满足包含这些位置，假设这个子区间是 \([l',r']\)，然后 \(0,1,2,...,i-1\) 的数对应的位置最左边和最右边分别是 \(left_i,right_i\)，那么有 \(l' \leq left_i,r' \geq right_i\)。这个 \([l',r']\) 的方案数显然是可以做乘法原理的，就是左端点方案数乘右端点的。就是 \((left_i-l+1) \times (r-right_i+1)\)。当然了，如果 \(left<l\) 或者 \(r<right\) 那么无论如何也不能满足把 \(0,1,2,...,i-1\) 全都选到了。

把上面的式子拆开变成 \(left_i*r - left_i*right_i + left_i - l*r + l*right_i - l + r - right_i + 1\)，这个东西的常数部分很好算。因为没有 \(left_i,right_i\) 的交叉项，所以只需要计算 \(\sum left_i,\sum right_i\)，这里满足条件的 \(i(left_i \geq l,right_i \leq r)\) 是一个前缀，所以先二分这个前缀，然后做前缀套进式子里算一下即可。

HihoCoder-1646

有 \(n\) 个包含 01? 的串，每个串的 ? 可以填成 0/1。求在所有情况下把这些串插入字典树得到的树的大小的和。
\(n \leq 20,|S| \leq 50\)。

字典树大小 这个东西很难刻画。

我们使用经典等价转换：字典树大小等价于本质不同前缀个数，也就是所有串前缀的并。

于是用容斥计算：\(\sum_S (-1)^{|S|-1} LCP(S)\)。

现在就是要看上面那个式子在每一种情况下的和，也就是所有的 \(S\) 在每一种情况的和再求和，其实就是交换了一下 sigma 的顺序。（\(\sum \sum_S (-1)^{|S|-1} LCP(S)=\sum_S (-1)^{|S|-1} \sum LCP(S)\)）这个也是经典的技巧，叫 sigma换序求和。

现在就是要算一个子集的串在每一种情况下的 \(LCP\) 之和，我们考虑用计数转 01。如何统计 \(LCP(S) \geq i\) 的情况数呢？那么显然要满足所有串的前 \(i\) 个字符相等，注意到每一位独立，分别考虑一下即可。这个部分很简单就不讲了。最后把每一个 \(i\) 统计的 \(\geq i\) 的数量加起来就是 \(S\) 对应的所有情况下的 \(LCP\) 之和。然后容斥起来就行。

计数转期望

如题，一些东西的总和显然等于期望乘上个数。看着似乎没啥用是吧，但是转成期望后会有很多有用的性质，并且呢也可以舍弃掉很多因为有个数参与的和的麻烦。在这里说你可能听不懂，依旧还是有几个题（

AGC030d

给定一个长度为 \(n\) 的数组 \(a\)，有 \(q\) 个操作形如交换位置为 \(x\) 和 \(y\) 的数，你可以选择每个操作是否执行。对于 \(2^q\) 种可能求所有情况的逆序对之和。
\(n,q \leq 3000\)

你会发现你完全不会做啊，我们能想到拆贡献到每一对数 \((i,j)\) 上来看有多少种情况满足这一对会贡献到答案里（\(a_i>a_j\)）。但是这个东西很难统计啊，即便你 \(dp\) 也很难转移。

考虑把这个东西转成期望，最后乘上 \(2^q\) 就是答案。这个期望 \(E\) 显然等于所有 \(i<j\) 满足 \(a_i>a_j\) 的概率之和。

那么我们令 \(f_{k,i,j}\) 表示前 \(k\) 个操作，\(a_i>a_j\) 的概率。那么现在要转移，就是要考虑第 \(k\) 个操作会怎么影响 \(a\) 的大小关系。显然只有 \(i=x,y\) 或者 \(j=x,y\) 的 \(f_{k,i,j}\) 才可能会发生改变，因为其它的 \(i,j\) 根本就没有任何一个位置上的数会变化。这个是好转移的：

f[x][j]=f[y][j]=v(f[x][j],f[y][j]);
f[j][x]=f[j][y]=v(f[j][x],f[j][y]);

其中 \(j\) 不等于 \(x,y\)，\(v(x,y)=\frac{x+y}{2}\)。

于是我们就解决了这个问题。

HDU-5396

来个简单题练练手。

有一个表达式，长的是这样：\(n\) 个数 \(a_1,a_2,...,a_n\)，每两个数之间有一个操作符号。每次可以选择一个操作符运算，直到只剩一个数，这个数就是表达式的结果。问所有情况下最后的数的和。
\(n \leq 500\)

我们还是考虑转期望。令 \(f_{l,r}\) 表示 \([l,r]\) 的答案。那么显然有转移 \(f_{l,r}=\frac{1}{r-l}\sum_{k=l}^{r-1} v(f_{l,k},f_{k+1,r},opt_k)\)，\(v(x,y,opt)\) 表示 \(x\ opt\ y\) 的结果。

最后答案即为 \(f_{1,n} \times (n-1)!\)。

ARC111F

给定 \(n,m,q\)，最开始有一个全是 0 的数组 \(a\)。有 \(q\) 个操作，有可能是：把一个区间的所有数和一个 \(v\) 取 min，取max，或者把一个区间的数的和加到答案 \(ans\) 里。区间随机，\(v\) 在 \(0\) 到 \(m-1\) 随机，问所有情况下 \(ans\) 的和。

史一样的数学题，太不可爱了。

但是她真的很妙。

还是先转期望，注意到查询的时候每一位是独立的，所以我们侧重点放在位置上的期望，然后每次算贡献就考虑包含的区间来算。

接着我们继续转化一步，把数值上的期望，接着再转化为 01 上的概率问题（\(v=\sum_{t=0} [v>t]\)，因为这里值域到底下顶到的是 \(0\)，所以这样写，其实你写成 \(\geq t\) 也是可以的）。
转化为对于每一个 \(t\) 满足 \(> t\) 的概率再求和，我选题的时候真是天才呜呜。

假设现在是对 \(t=i\) 计算。

对于这种区间取 \(min/max\) 的题，我们一种常用的思维是去考虑哪些操作是会被我们修改的。显然只有取 \(min\) 且 \(v \leq i\) 或者取 \(max\) 且 \(v>i\) 会改变，否则在 \([a_j>i]\) 这个东西上面没有任何改变的可能。同时，我们还发现，如果修改了，那就相当于把一个区间覆盖成 0/1。

我们用 \(w_j\) 表示修改了 \(j\) 的概率，修改了 j 这个东西等价于：这次操作是修改且这次操作的区间包含 j 且这次操作满足上面说的条件，概率就是乘法原理就行。写一下就是 \(w_j=\frac{2mj(n-j+1)}{n(n+1)(2m+1)}\)。

记 \(k\) 次操作后 \(a_j>i\) 的概率为 \(f_{k,j}\)，\(a_j\) 的期望为 \(g_{k,j}\)。

对于 \(f\) 怎么求呢？只有当 \(j\) 最后一次有效的操作被做了 max 的有效覆盖的情况下才会满足 \(a_j>i\)，所以有 \(f_{k,j}=\frac{m-i-1}{m}(1-(1-p_j)^k)\)。

根据前面的 01 转换，\(g\) 其实就是把 \(f\) 做一个前缀和，那么有 \(g_{k,j}=\sum_{t=0}^{m-1} f_{k,j}=\frac{m-1}{2}(1-(1-p_j)^k)\)。

我们发现这里和枚举的 \(i\) 无关了！这是个非常好的事情。

推到这里了，可以收获了。这个时候就在每一个时刻看这个时候做 3 操作可以得到的和的期望，也就是对于每一个数看一下期望，对于这一个数的期望就是这一次选的是操作 3 且包含这个数的概率乘上这个数的期望。

\(E=\sum_{t=0}^{q-1}\sum_{i=1}^n \frac{i(n-i+1)}{\frac{n(n+1)}{2}} \times \frac{1}{2m+1} \times g_{t,i}\)，注意到第二个 sigma 到 \(g_{t,i}\) 中间那部分只和 \(i\) 相关，所以拎到前面来 \(E=\sum_{i=1}^n \frac{i(n-i+1)}{\frac{n(n+1)}{2}} \times \frac{1}{2m+1} \times \sum_{t=0}^{q-1} g_{t,i}=\sum_{i=1}^n \frac{i(n-i+1)}{n(n+1)} \times \frac{m-1}{2m+1} \times (q-\frac{(1-p_i)^t}{p_i})\)。

这样期望就可以 \(O(n)\) 计算了。

最后我们再乘上方案数也就是 \((\frac{(N+1)N}{2}\cdot(M+M+1))^Q\) 即可。