YbtOJ 884「线性基」连通的图
题目链接：YbtOJ #884
小 A 有一张 n 个点，n k-1 条边的无向连通图。
他想知道有多少种方案删去图中若干条边（包括一条边都不删），满足剩下的图依然连通。
由于方案数可能很大，你只需输出答案对 998244353 取模的结果。
1le nle 10^5，1le kle10
Solution
比较神奇的题。
任意找出一棵生成树，给每条非树边设置一个单独的权值 2^i。
对所有树边，规定它的权值为所有覆盖它的非树边的权值异或和。要实现这一过程，只需利用树上差分给每条非树边覆盖的树边打上异或标记，最后 dfs 遍历一遍做个子树异或和即可求出所有树边的权值。
发现一张图不连通，充要于 **删去的边集中存在一个子集异或和为 0**。
要判断加入一个数后是否存在子集异或和为 0，只要判断能否插入线性基即可。（不能说明线性基内若干数异或和与它相同，则异或上它之后就得到了 0）
现在我们求出了每条边的权值，由于这里同种权值的边并没有区分，且不可能同时加入（显然两个相同权值异或为 0），我们可以直接用桶存下每种权值的边数。
然后就是暴搜，枚举每种权值的边选或不选即可。
Code
代码语言：javascript复制#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("%dn",dfs(0,0)),0;
}
