题目
题目背景
数学能够成为严谨的科学学科，离不开这三条公理的支持：
- 若一个命题无法被证伪，则它是正确的。
- 若一个命题无法被证明，则它是错误的。
- 若这么做的人不是
O
U
Y
E
\sf OUYE
OUYE，则前两条都是错误的。
题目描述
给出一个简单无向图
G
=
(
V
,
E
)
G=(V,E)
G=(V,E)，给出
m
m
m 个点集
S
1
,
S
2
,
…
,
S
m
S_1,S_2,\dots,S_m
S1?,S2?,…,Sm?，问有多少个生成树
T
T
T 满足
S
i
??
(
1
?
i
?
m
)
S_i\;(1\leqslant i\leqslant m)
Si?(1?i?m) 是树
T
T
T 上的连通块。
数据范围与提示
∣
V
∣
?
500
|V|\leqslant 500
∣V∣?500 且
m
?
2000
m\leqslant 2000
m?2000 。显然
∣
E
∣
?
(
∣
V
∣
2
)
|E|\leqslant{|V|\choose 2}
∣E∣?(2∣V∣?) 。
我的思路
从一些简单的情况想起。若
m
=
0
m=0
m=0 就是矩阵树定理裸题。
若
m
=
1
m=1
m=1，考虑
∣
S
1
∣
=
2
|S_1|=2
∣S1?∣=2，即存在一条必选的边，则直接选择它然后缩点。推广到
∣
S
1
∣
?
2
|S_1|\geqslant 2
∣S1?∣?2，只需要先对该连通块建立生成树（矩阵树定理求生成树个数）然后缩点，再做全局的矩阵树定理。
若
m
=
2
m=2
m=2，考虑
S
1
∩
S
2
=
?
S_1\cap S_2=\varnothing
S1?∩S2?=?，则二者独立，分别缩点。否则，我们注意到树上连通块的交集仍然是连通块，所以
S
′
=
S
1
∩
S
2
S'=S_1\cap S_2
S′=S1?∩S2? 也是连通块。将
S
′
S'
S′ 缩点后则
∣
S
1
∩
S
2
∣
=
1
|S_1\cap S_2|=1
∣S1?∩S2?∣=1，这样的连通块也是独立的，又可以分别缩点了。
推广到任意
m
m
m，直观来看似乎只需处理每种
S
S
S 的交集。这是非常感性的；从特殊到一般不要想当然。我在过程中就犯了下面的诸多错误。
其实
m
>
2
m>2
m>2 的时候，只需要依次合并信息。先令
T
=
V
T=V
T=V 即全集，然后检查
m
m
m 个
S
i
S_i
Si?，在
∣
S
i
∩
T
∣
>
1
|S_i\cap T|>1
∣Si?∩T∣>1 时令
T
=
S
i
∩
T
T=S_i\cap T
T=Si?∩T 。最后对
T
T
T 运用矩阵树定理。重复该过程即可。
先别算复杂度。我们凭什么能缩点？已经连通的点并不等价。比如三元环，
S
1
=
{
1
,
2
}
S_1=\{1,2\}
S1?={1,2} 而
S
2
=
{
2
,
3
}
S_2=\{2,3\}
S2?={2,3}，答案为
1
1
1 。然而缩点
S
1
S_1
S1? 会导致新图为
E
′
=
{
(
1
′
,
2
)
,
(
1
′
,
2
)
}
E'=\{(1',2),(1',2)\}
E′={(1′,2),(1′,2)}，求出答案为
2
2
2 。
所以，我们实际上是 临时缩点，在求某个点集
T
T
T 的生成树数量时，将
T
T
T 中已经连通的点视为一个点。用并查集维护哪些点已经连通。同时，原本的
∣
S
i
∩
T
∣
>
1
|S_i\cap T|>1
∣Si?∩T∣>1 也要改为
S
i
∩
T
S_i\cap T
Si?∩T 尚未完全连通。缩点的问题就解决了。
无论复杂度如何，你会发现三元环上
m
=
(
3
2
)
m={3\choose 2}
m=(23?) 判不出无解（即每条边都被
S
i
S_i
Si? 指定了）。因为
∣
S
1
∩
S
2
∣
=
1
|S_1\cap S_2|=1
∣S1?∩S2?∣=1 时二者独立，前提是我们料想它们的连通性互不影响——这在它们确实构成树时，是毋庸置疑的。然而无解时呢？
需要判断无解。其实简单，在并查集合并
A
,
B
A,B
A,B 两个点集时，若某个
S
i
S_i
Si? 满足
S
i
∩
A
≠
?
S_i\cap A\ne\varnothing
Si?∩A?=? 且
S
i
∩
B
≠
?
S_i\cap B\ne\varnothing
Si?∩B?=? 且当前操作点集
T
?
S
i
T\nsubseteq S_i
T?Si?，则无解。因为
T
?
S
i
T\nsubseteq S_i
T?Si? 说明
∣
T
∩
S
i
∣
?
1
|T\cap S_i|\leqslant 1
∣T∩Si?∣?1，即 “理论上不应影响
S
i
S_i
Si? 中点的连通性”。而现在影响了，肯定无解。
终于，到了优化复杂度的时候。首先是找
T
T
T 。共
n
n
n 轮，每轮求
k
k
k 次大小为
n
n
n 的集合交，并判断它是否完全连通。用
b
i
t
s
e
t
\tt bitset
bitset 求出集合并，然后找到其中任意一个元素——用 _Find_first 函数，虽说似乎不太正规——设为
x
x
x 。对并查集的每个连通块，用
b
i
t
s
e
t
\tt bitset
bitset 维护其中的元素，那么只需要判断
x
x
x 所在连通块对应的点集是否包含
S
i
∩
T
S_i\cap T
Si?∩T 。复杂度
O
(
k
n
2
ω
)
\mathcal O({kn^2\over\omega})
O(ωkn2?) 。
接着是矩阵树定理，总复杂度
O
(
n
3
)
\mathcal O(n^3)
O(n3) 不解释。然后是判断无解。共判断
O
(
n
)
\mathcal O(n)
O(n) 次，每次
O
(
k
)
\mathcal O(k)
O(k) 个
O
(
n
ω
)
\mathcal O({n\over\omega})
O(ωn?) 的
b
i
t
s
e
t
\tt bitset
bitset 判断，也是
O
(
k
n
2
ω
)
\mathcal O({kn^2\over\omega})
O(ωkn2?) 的。
最后是维护并查集信息。只有
O
(
n
2
ω
)
\mathcal O({n^2\over\omega})
O(ωn2?)，不用考虑了。总复杂度
O
(
k
n
2
ω
+
n
3
)
\mathcal O({kn^2\over\omega}+n^3)
O(ωkn2?+n3) 搞定。
正解思路
略
constructive
\text{constructive}
constructive 。但确实具有美感，可以讲讲。
我的做法 为何复杂？因为
∣
S
1
∩
S
2
∣
=
1
|S_1\cap S_2|=1
∣S1?∩S2?∣=1 时，二者也独立。这说明 点不是基本元素。生成树实际上是选择边的过程。于是我们考虑一条边被
S
i
S_i
Si? 包含的次数，记
λ
(
u
,
v
)
=
∑
[
u
∈
S
i
∧
v
∈
S
i
]
\lambda(u,v)=\sum[u\in S_i\land v\in S_i]
λ(u,v)=∑[u∈Si?∧v∈Si?] 。结论是 最大生成树即为所求，当然，需要权值和恰好为
∑
(
∣
S
i
∣
?
1
)
\sum(|S_i|-1)
∑(∣Si?∣?1) 。
何故？显然
S
i
S_i
Si? 在
λ
\lambda
λ 上的系数最多贡献
(
∣
S
i
∣
?
1
)
(|S_i|{-}1)
(∣Si?∣?1)，而且必须达到。所以只能是最大生成树。求最大生成树个数，只需对每种权值的边分别做一次即可。时间复杂度
O
(
n
3
+
n
2
k
ω
)
\mathcal O(n^3+{n^2k\over\omega})
O(n3+ωn2k?)，代码实现想必很简单。
代码
正解思路 代码可见最强者的博客。欲知谁最强，重读《题目背景》。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <bitset>
#include <vector>
typedef long long llong;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
int a = 0, c = getchar(), f = 1;
for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
for(; isdigit(c); c=getchar()) a = a*10+(c^48);
return a*f;
}
const int MOD = 998244353;
inline void modAddUp(int &x, const int &y){
if((x += y) >= MOD) x -= MOD;
}
inline llong qkpow(llong b, int q){
llong a = 1;
for(; q; q>>=1,b=b*b%MOD) if(q&1) a = a*b%MOD;
return a;
}
const int MAXN = 503;
int mat[MAXN][MAXN];
int getDet(int n){
int res = 1;
for(int i=1,id; i<=n; ++i){
rep(j,id=i,n) if(mat[j][i]){
id = j; break;
}
if(mat[id][i] == 0) return 0;
int* const _end = mat[i]+n+1;
if(id != i){
for(int *l=mat[i]+i,*r=mat[id]+i; l!=_end; ++l,++r)
std::swap(*l,*r);
res = MOD-res;
}
res = int(llong(res)*mat[i][i]%MOD);
llong inv = qkpow(mat[i][i],MOD-2);
for(int *j=mat[i]+i; j!=_end; ++j)
*j = int((*j)*inv%MOD);
rep(j,i+1,n) if(mat[j][i]){
const llong f = MOD-mat[j][i];
for(int *l=mat[i]+i,*r=mat[j]+i; l!=_end; ++l,++r)
*r = int(((*r)+f*(*l))%MOD);
}
}
return res;
}
namespace UFS{
int fa[MAXN];
std::bitset<MAXN> cov[MAXN];
void init(const int &n){
rep(i,1,n) fa[i] = i, cov[i].set(i);
}
inline int find(int a){
if(fa[a] == a) return a;
return fa[a] = find(fa[a]);
}
void merge(int a, int b){
cov[fa[b]] |= cov[fa[a]];
fa[fa[a]] = fa[b];
}
}
const int MAXK = 2000;
std::bitset<MAXN> bel[MAXK];
bool link(int a, int b, const std::bitset<MAXN> &now, const int &k){
a = UFS::find(a), b = UFS::find(b);
if(a == b) return true;
rep0(i,0,k) if(((~bel[i])&now).any())
if((UFS::cov[a]&bel[i]).any())
if((UFS::cov[b]&bel[i]).any()) return false;
UFS::merge(a,b); return true;
}
int haxi[MAXN], xjx[MAXN];
int gra[MAXN][MAXN]; char str[MAXN+10];
int main(){
int n = readint(), k = readint();
rep0(i,1,n) rep(j,i+1,n)
gra[i][j] = gra[j][i] = readint();
for(int i=0; i!=k; ++i){
scanf("%s",str+1);
rep(j,1,n) bel[i].set(j,str[j]^48);
}
UFS::init(n); int ans = 1;
rep0(_,1,n){
std::bitset<MAXN> now; now.set();
rep0(i,0,k){
std::bitset<MAXN> jj = now&bel[i];
if(jj.count() <= 1) continue;
int rt = int(jj._Find_first());
if(((~UFS::cov[UFS::find(rt)])&jj).any())
now = jj;
}
memset(xjx+1,0,n<<2); int tot = 0, rt = 0;
rep(i,1,n) if(now.test(i)){
int x = UFS::find(i);
if(!haxi[x]) haxi[x] = ++ tot;
xjx[i] = haxi[x], rt = x;
rep0(j,1,i) if(xjx[j])
modAddUp(mat[xjx[i]][xjx[j]],gra[i][j]);
}
rep0(i,1,tot) mat[i][i] = 0;
rep0(i,1,tot) rep(j,i+1,tot){
const int v = (mat[i][j]+mat[j][i])%MOD;
mat[i][j] = mat[j][i] = MOD-v;
modAddUp(mat[i][i],v), modAddUp(mat[j][j],v);
}
ans = int(llong(ans)*getDet(tot-1)%MOD);
rep(i,1,n) if(haxi[i]){
if(link(i,rt,now,k) == false){
puts("0"); return 0;
}
haxi[i] = 0;
}
rep(i,1,tot) memset(mat[i]+1,0,tot<<2);
}
printf("%d\n",ans);
return 0;
}
|