OI - 分割 (NOI.AC) | Lucky_Glass's Blog
0%

OI - 分割 (NOI.AC)

bitset 真好用


Part1. 题面

给定全集 $C=\{1,2,\cdots,n\}$。

在全集 C 的意义下,当一个子集 E 和一个 有序 对 (X,Y)(X,Y 都是 C 的子集)满足 $\begin{cases}X\subseteq E\\Y\cap E=\varnothing\end{cases}$ 或 $\begin{cases}Y\subseteq E\\X\cap E=\varnothing\end{cases}$ 时,称 “E 分割 (X,Y)”,即 “(X,Y) 被 E 分割”。

再给出 m 个 C 的子集 $A_i$ 和整数 k。

求有多少个有序对 (X,Y) 满足 (X,Y) 至少被一个给定的子集 $A_i$ 分割,且 X,Y 的大小都为 k。

数据规模:$1\le m\le18,1\le n\le100,1\le k\le\left\lfloor\frac n2\right\rfloor$


Part2. 解析

>> Tip.
可以用 bitset<100> 来维护一个子集!

Part2/1. 初步容斥

这种直接算不方便的计数问题怎么做?常见的可以是计数DP,也可以是容斥原理套用一大堆组合数学的式子。

把所有 m 个 $A_i$ 作为一个新的集合 $S$ 的元素,那么可以这样容斥:

Part2/2. 暴力思路

根据上面的容斥,就可以得到一个暴力的思路 —— DFS 决策每个集合是否一定分割 (X,Y),然后容斥计数。

>> Tip
$\overline E$ 表示 E 在全集 C 意义下的补集

但是 (X,Y) 被 E 分割有两种情况:
① $\begin{cases}X\subseteq E\\Y\cap E=\varnothing\end{cases}$ 即 $\begin{cases}X\subseteq E\\Y\subseteq \overline E\end{cases}$;
② $\begin{cases}Y\subseteq E\\X\cap E=\varnothing\end{cases}$ 即 $\begin{cases}X\subseteq \overline E\\Y\subseteq E\end{cases}$。

那么我们除了要决策 $A_i$ 是否一定分割 (X,Y),还要决策 $A_i$ 分割 (X,Y) 的方式是①还是②。

因此对于每个 $A_i$ 有三种状态:
a. $A_i$ 不一定分割 (X,Y),也就是对 (X,Y) 不造成影响;
b. $X\subseteq A_i$ 且 $Y\subseteq \overline {A_i}$;
c. $X\subseteq\overline {A_i}$ 且 $Y\subseteq A_i$;

枚举每个 $A_i$ 的状态,再组合数计算 (X,Y) 的数量,容斥得到答案即可。

>> Tip
枚举出每个 $A_i$ 的状态过后,我们可以得到对于集合 X,Y 的类似于 $X\subseteq E_x,Y\subseteq E_y$ 的限制。这样的话,(X,Y) 的数量就为 $C_{|E_x|}^kC_{|E_y|}^k$。

>> Tab
$O(w)$ 是 bitset 的常数

时间复杂度是枚举 m 个 $A_i$ 的 3 种状态 $O(3^m)$ 乘上 bitset 的复杂度 $O(nw)$,也就是 $O(3^mnw)$。

但是还可以优化一下,把直接枚举 $A_i$ 的状态改成 DFS 依次决策 $A_i$ 的状态,中途剪枝。(据说这样能 AC,而且剪枝的效率极高,比标程快 10 倍……真暴力碾标算

Part2/3. 优化暴力

如果直接枚举 $A_i$ 的 $3^m$ 种状态,会有很多状态最后得到的 $X\subseteq E_x,Y\subseteq E_y$ 限制中,$\underline{E_x,E_y}$ 是空集,也就浪费了时间。

我们考虑先枚举哪些 $A_i$ 会对 (X,Y) 造成影响,复杂度是 $O(2^m)$ 的,然后再枚举全集 C 中的一个元素 t,如果 $t\in X$,那么可以推导出对 (X,Y) 造成影响的 $A_i$ 是怎样造成影响的:

  1. 如果 $t\in A_i$,那么一定是 $X\subseteq A_i$;
  2. 如果 $t\not\in A_i$,那么一定是 $X\subseteq \overline {A_i}$;

(我觉得非常显然嘛……)

但是我们发现对于同样的 $A_i$,不同的 t 可能使得 $A_i$ 对 (X,Y) 的影响方式完全一样,就会算重,于是需要判一下重,防止计算同一个方案多次。

时间复杂度变成了 $O(nm2^m\times nw)$。(因为要判重,复杂度多了一个 m)

Part2/4. 正解

不妨倒过来 —— 先枚举 t!然后再 DFS 决策 $A_i$ 会不会对 (X,Y) 造成影响,同时维护 $E_x,E_y$。然后判重用 字典树 !字典树的一个节点有 3 个儿子,分别表示 $A_i$ 的 3 种状态。这样显然是用空间换时间,不过非常划算。

于是在时间复杂度上就非常玄学地少了 $O(m)$ ~

最后复杂度为 $O(n2^m\times nw)$。


Part3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*Lucky_Glass*/
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100,M=18,MOD=998244353,SIZE=5e7;
#define fix(x) (int((x%MOD+MOD)%MOD))

struct MNUM{
int num;
MNUM(){}
MNUM(int _num):num(_num){}
MNUM operator +(const MNUM cur)const{return fix(1ll*num+cur.num);}
MNUM operator -(const MNUM cur)const{return fix(1ll*num-cur.num);}
MNUM operator *(const MNUM cur)const{return fix(1ll*num*cur.num);}
MNUM operator +=(const MNUM cur){return *this=(*this)+cur;}
MNUM operator -=(const MNUM cur){return *this=(*this)-cur;}
MNUM operator *=(const MNUM cur){return *this=(*this)*cur;}
};

int n,m,k;
MNUM ans,fac[N+3],invfac[N+3];
bitset<N> bt[2][M],full;
bool inpin[N];
int ch[SIZE][3],polcnt,root;

MNUM fC(int cura,int curb){
if(cura>curb) return 0;
return fac[curb]*invfac[cura]*invfac[curb-cura];
}
void DFS(int &u,int now,int nchs,bitset<N> inset,bitset<N> outset){
if(!u){ //这样就可以判重了!
u=++polcnt;
if(now==m){
MNUM delta=fC(k,inset.count())*fC(k,outset.count());
if(nchs&1) ans+=delta;
else ans-=delta;
return;
}
}
else if(now==m) return;
DFS(ch[u][2],now+1,nchs,inset,outset);
//判断 Ai 对 (X,Y) 怎么影响
if(inpin[now]) DFS(ch[u][0],now+1,nchs+1,inset&bt[0][now],outset&bt[1][now]);
else DFS(ch[u][1],now+1,nchs+1,inset&bt[1][now],outset&bt[0][now]);
}
MNUM QPow(MNUM cura,int curb){
MNUM resu(1);
while(curb){
if(curb&1) resu*=cura;
cura*=cura;
curb>>=1;
}
return resu;
}
void Init(){
fac[0]=1;for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i;
invfac[N]=QPow(fac[N],MOD-2);
for(int i=N-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1);
}
int main(){
Init();
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++) full[i]=1;
for(int i=0;i<m;i++){
int l;scanf("%d",&l);
for(int j=0;j<n;j++) inpin[j]=false;
while(l--){
int inum;scanf("%d",&inum);
inpin[inum-1]=true;
}
for(int j=0;j<n;j++)
if(inpin[j]) bt[0][i][j]=1;
else bt[1][i][j]=1;
}
polcnt=0;
ans=fC(k,n)*fC(k,n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
inpin[j]=bt[0][j][i];
DFS(root,0,0,full,full);
}
printf("%d\n",ans.num);
return 0;
}

The End

Thanks for reading!

终于写完了……