YbtOJ 884「线性基」连通的图

(Updated: )
oi
,

题目链接：YbtOJ #884

小 A 有一张 $n$ 个点，$n+k-1$ 条边的无向连通图。

他想知道有多少种方案删去图中若干条边（包括一条边都不删），满足剩下的图依然连通。

由于方案数可能很大，你只需输出答案对 $998244353$ 取模的结果。

$1\le n\le 10^5$，$1\le k\le10$

Solution

比较神奇的题。

任意找出一棵生成树，给每条非树边设置一个单独的权值 $2^i$。

对所有树边，规定它的权值为所有覆盖它的非树边的权值异或和。要实现这一过程，只需利用树上差分给每条非树边覆盖的树边打上异或标记，最后 dfs 遍历一遍做个子树异或和即可求出所有树边的权值。

发现一张图不连通，充要于 **删去的边集中存在一个子集异或和为 $0$**。

要判断加入一个数后是否存在子集异或和为 $0$，只要判断能否插入线性基即可。（不能说明线性基内若干数异或和与它相同，则异或上它之后就得到了 $0$）

现在我们求出了每条边的权值，由于这里同种权值的边并没有区分，且不可能同时加入（显然两个相同权值异或为 $0$），我们可以直接用桶存下每种权值的边数。

然后就是暴搜，枚举每种权值的边选或不选即可。

Code

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
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
Cn int N=1e5+10,p=998244353;
int n,k,g[N],C[(1<<11)+5];
vector<int> G[N],v;
#define pb push_back
I void DFS(CI x,CI fa){for(auto i:G[x]) i^fa&&(DFS(i,x),g[x]^=g[i]);x>1&&++C[g[x]];}
struct LineBasic{
    int d[13];I int Add(LL x){
        RI i,flg=0;for(i=10;~i;i--) if(x>>i&1)
            if(d[i]) x^=d[i];else return d[i]=x;
        return 0;
    }
}A[13];
I int dfs(CI x,CI nw){if(x>=v.size()) return 1;RI S=dfs(x+1,nw);if(A[nw+1]=A[nw],A[nw+1].Add(v[x])) S+=1LL*C[v[x]]*dfs(x+1,nw+1)%p,S%=p;return S;}
int main(){
    freopen("connected.in","r",stdin),freopen("connected.out","w",stdout);
    RI i,x,y;for(read(n,k),i=1;i<=n+k-1;i++) read(x,y),i<n?G[x].pb(y),G[y].pb(x),0:(++C[1<<i-n],g[x]^=(1<<i-n),g[y]^=(1<<i-n),0);
    for(DFS(1,0),i=1;i<(1<<k);i++) C[i]&&(v.pb(i),0);return printf("%d\n",dfs(0,0)),0;
}