题目链接

https://acm.hdu.edu.cn/showproblem.php?pid=6001

题解

设$f(S)$表示有多少种选问卷的情况使得$S$中所有元素都不是好问题

设$ans[S]$表示选择的问题集合是$S$时,有多少种选择问卷的方案使得它们全部是好问题

那么由容斥原理,$ans[S]=2^n+\sum\limits_{S_2\subseteq S}(-1)^{t(S)}f(S)$,其中$t(S)$为$S$中元素个数

考虑如何预处理$f(S)$

对于每个问卷$x$,设$tag[x]=\sum\limits_{i=1}^{m}2^i[a[x][i]=Y]$,即如果第$i$个问题答案是yes那第$i$位就是$1$

设$cnt[p]$表示有多少$x$的$cnt[x]=p$

那么对于一种使得所有问题都不是好问题的选择方案,选择的所有问卷的$tag$一定相等

所以容易得出$f(2^n-1)=1+\sum\limits_{i=0}^{2^m-1}(2^{cnt[i]}-1)$

最前面那个$1$表示取空集

假设我们已经算出$f(S)$,考虑$S$去掉一个元素$i$得到的新集合$S_2$

那么此时$i$是不是好问题就无所谓了,所以可以直接把$i$这一位给“删掉”

具体实现中,可以对于所有包含$i$的集合$T$,让$cnt[T-i]+=cnt[T]$,然后这个$cnt[T]$就当它不存在,这样就相当于默认第$i$位是$0$(操作A)

(这里不是做减法,只是表示$T$集合去掉元素$i$)

那么对于$f(S_2)$,枚举$S_2$的所有子集$S_3$(显然除了$S_3$以外的那些集合$T$的$cnt[T]$已经被我们当成不存在了),有$f(S_2)=1+\sum\limits_{S_3\subseteq S_2}(2^{cnt[S_3]}-1)$

然后考虑用一个dfs,我们已经算出$f(S)$了,这时进行上面那个操作A,然后往$S_2$递归,就能算出$f(S_2)$

这一步的复杂度是$O(m^3)$的,这样就处理出了所有的$f(S)$

然后回到上面$ans[S]=2^n+\sum\limits_{S_2\subseteq S}(-1)^{t(S)}f(S)$,这一步的复杂度也是$O(m^3)$的,总时间复杂度为$O(tm^3)$(时限40s?)

代码

暂时还没有

评论