CF1299D - Around the World

题目大意

给定一张带权无向图,满足经过1号点不存在长度$>3$的简单环

求删除1号点所连边的一个子集,使得剩下的边构成的图满足

不存在一条 非完全重复 回路 异或和为0

非完全重复即所有边恰好被经过偶数次的回路

边权$<32$


分析

考虑如何判定0回路

1.任意一个回路由同一连通块内的环叠加产生

2.将所有$\text{dfs}$树上的环边提取出来,无法加入线性基时则存在0回路

线性基是重要的判断0回路的方法,因此考虑直接将线性基压进状态进行$dp$


dp

删除1所连边后,对于每个连通块考虑计算

设连通块内环边的线性基为$D$(加入每条都能成功插入,否则直接跳过该连通块)

包含$C$条连接1的边

仍需考虑经过1的环边,题目限制了这样的环边在每个连通块内最多有一条

不妨提取这条边,设其所在三元环权为$L$

那么转移分为3种

1.不选这个连通块

2.选择连通块内所有边,但是不选三元环,即$3\cdot 2^{C-2}-1$ (如果存在$L$)

暴力合并$dp$状态中的线性基和$D$即可,依次插入$D$中的每条基

3.额外再选择$L$,$2^{C-2}$

状压线性基容易发现线性基最多有15个位置可能出现1,可以暴力二进制存下来

实际上,合法的线性基通过高斯消元之后种类非常少,因此复杂度有保证

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
const int N=1e5+10,P=1e9+7;

int n,m;
vector <Pii> G[N];

ll qpow(ll x,ll k=P-2) {
ll res=1;
for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
return res;
}

#define Gauss rep(i,0,4) if(d[i]) rep(j,i+1,4) if(d[j]&(1<<i)) d[j]^=d[i];\
drep(i,4,0) D=(D<<(i+1))|d[i];

int Ins(int &D,int x){
int d[5];
rep(i,0,4) d[i]=D&((1<<(i+1))-1),D>>=i+1;
int f=0;
drep(i,4,0) if(x&(1<<i)) {
if(d[i]) x^=d[i];
else { f=1,d[i]=x; break; }
}
if(!f) return 0;
Gauss;
return 1;
}

int Uni(int &D,int E){
if(!E) return 1;
int d[5];
rep(i,0,4) d[i]=D&((1<<(i+1))-1),D>>=i+1;
rep(i,0,4) {
int x=E&((1<<(i+1))-1); E>>=i+1;
if(!x) continue;
int f=0;
drep(i,4,0) if(x&(1<<i)) {
if(d[i]) x^=d[i];
else { f=1,d[i]=x; break; }
}
if(!f) return 0;
}
Gauss;
return 1;
}

struct Table{
int val[1<<15],a[1<<15],c;
void Add(int x,int v) {
if(!val[x]) a[c++]=x;
val[x]+=v,Mod1(val[x]);
}
void clr(){
rep(i,0,c-1) val[a[i]]=0;
c=0;
}
} dp[2];

int vis[N],dfn,dis[N],D,F,E[N],L,C;
void dfs(int u) {
vis[u]=++dfn;
if(~E[u]) C++;
for(Pii i:G[u]) if(i.first!=1) {
int v=i.first;
if(~E[u] && ~E[v]) L=E[u]^E[v]^i.second; // 找到了一个经过1的三元环
if(!vis[v]) dis[v]=dis[u]^i.second,dfs(v);
else if(vis[v]>vis[u]) {
F&=Ins(D,dis[v]^dis[u]^i.second);
}
}
}

int main(){
n=rd(),m=rd();
rep(i,1,m) {
int u=rd(),v=rd(),w=rd();
G[u].pb(mp(v,w)),G[v].pb(mp(u,w));
}
rep(i,1,n) E[i]=-1;
for(Pii i:G[1]) E[i.first]=i.second;
int cur=0;
dp[0].Add(0,1);
for(Pii i:G[1]) {
int v=i.first;
if(vis[v]) continue;
F=1,D=C=0,L=-1,dfs(v);
if(!F) continue;
dp[!cur].clr();
if(~L) C-=2;
C=qpow(2,C);
rep(i,0,dp[cur].c-1) {
int x=dp[cur].a[i],y=dp[cur].val[x];
dp[!cur].Add(x,y);
if(Uni(x,D)) {
dp[!cur].Add(x,((~L?3ll:1ll)*C-1)*y%P);
if(~L && Ins(x,L)) dp[!cur].Add(x,1ll*y*C%P);
}
}
cur^=1;
}
int ans=0;
rep(i,0,dp[cur].c-1) (ans+=dp[cur].val[dp[cur].a[i]])%=P;
printf("%d\n",ans);
}