主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
[ARC188E] Mirror and Order 题解
最后更新于 2025-06-15 21:43:55
作者
rqoi031
分类
题解
复制 Markdown
查看原文
更新内容
参考了 maspy 的题解。 感觉这个容斥非常厉害，所以写篇题解记录一下。 先转化为若干个点，分成三类，求把它们连成若干个环，不存在只有第一或二类点的环的方案数。 假设这三类点分别有 $N_1,N_2,N_3$ 个，考虑容斥。 我们先钦定一些不合法的环，假设全 $1$ 的环钦定了 $k_1$ 个，全 $2$ 的钦定了 $k_2$ 个，先考虑容斥系数，为 $(-1)^{k_1+k_2}$。 再考虑方案数，发现我们还需要枚举构成这些环的点数，假设分别为 $n_1,n_2$，那么方案数显然为 $\binom{N_1}{n_1}{n_1\brack k_1}\binom{N_2}{n_2}{n_2\brack k_2}(N_1+N_2+N_3-n_1-n_2)!$，其中 $n\brack k$ 表示第二类斯特林数。 直接容斥显然是 $\Theta(N^4)$ 的，但是我们有一个很好的结论： $$ \forall n\geq2,\sum_k(-1)^k{n\brack k}=0 $$ 所以我们只需要枚举 $n_1,k_1,n_2,k_2\leq 1$ 的部分，时间复杂度 $\Theta(N)$。 [代码](https://atcoder.jp/contests/arc188/submissions/60223584)
正在渲染内容...
点赞
0
收藏
0
