模拟赛 #39 T3 笔记

前置知识：插板法，二项式反演。

简单的转换：算出方案数再除以总方案数。

简单的转换：大于和小于本质相同，因此大于的方案数 $\mathrm{cnt}(>)$ 是 ${\displaystyle \frac{\mathrm{all}-\mathrm{cnt}(=)}{2}}$。

现在变成求长度为 $n$，值域为 $[0,m]$ 且和相等的两个序列 $(a,b)$ 的对数。

形式化一下

$$\sum a=\sum b$$$$(\sum a)-(\sum b)=0$$

$min(\underset{1}{max},\underset{2}{max})$ 不好做可以想到转换为 $\underset{1}{max}+\underset{2}{max}-max()$（P10764），现在是 $\sum -\sum$ 不好做，所以接下来就是惊为天人的一步转换。

$$(\sum a)+(\sum m-b)-nm=0$$$$(\sum a)+(\sum m-b)=nm$$

如果没有 $a,b\subseteq [0,m]$ 的限制，这个使用传统插板法就做完了，即 $(\genfrac{}{}{0ex}{}{nm+2n-1}{2n-1})$。

现在考虑 $[0,m]$ 的限制，考虑钦定若干个数不满足这个限制，被钦定的数一定 $\ge m+1$，假如钦定了 $x$ 个数，那么只需要求

$$(\sum a)+(\sum m-b)=nm-x(m+1)$$

没有限制的方案数即可。

最后使用二项式反演就能求出恰好不满足 $0$ 个限制的方案数，即

$$\sum _{i=0}^{\lfloor \frac{nm}{m+1}\rfloor }(-1{)}^{i-0}(\genfrac{}{}{0ex}{}{i}{0})\times (\genfrac{}{}{0ex}{}{2n}{i})(\genfrac{}{}{0ex}{}{nm-i(m+1)+2n-1}{2n-1})$$

总数显然是 $m^{2n}$。

时间复杂度 $O(Tn)$。