讨论/题目交流/一个大集合内不含互斥组的子集计数怎么解决?/
一个大集合内不含互斥组的子集计数怎么解决?

已知集合A为{1,2,...,n},集合B的元素是若干A的二元组.

考虑这样的集合T,T是A的子集,对于B中的(i,j),T中不能同时出现i,j.

这样的T一共有多少个?

-----------更新分割线-----------

本题是从atcoder 168 的e题抽象出来的,原始题目是一堆二维向量,向量正交则互斥。

我的抽象缺失了一个要点。a平行b,c平行d,那么ac正交等价于bd正交,也就是可以按平行关系分类。
于是相应地,我的A集可以划分为A_0,A_1,A_2,...的无交并,A_0跟别的不互斥,A_{2k-1}的恰好跟A_{2k}的互斥,这样就可以用乘法原理计算那道题了。

那么,不考虑atcoder 168 e原题的特殊关系,仅仅就我一开始抽象出来的结构,B可以为任何有意义的情况,有没有O(n^3)以下的算法?

展开讨论
三角和发起于 2020-05-18
最近编辑于 2020-05-20

好像就是求子集(i, j),然后分类计算 含i,含j,都不含,各有几个可能的T,加起来。

展开全部 3 讨论