题解 P7717 「EZEC-10」序列

很好的题。

首先条件可以转化为 $a_{y_i}=a_{x_i}\oplus z_i$，因此 $a_{x_i}$ 一旦确定了，那么 $a_{y_i}$ 同样也就确定了。

我们考虑连边：对于每条限制 $(x_i,y_i,z_i)$，我们在 $x_i,y_i$ 间连双向边，边权为 $z_i$。

那么对于一个连通块，只要一个数确定了，所有数就都确定了。只需要计算每个连通块的答案然后乘起来就行了。

我一开始以为答案就是 $k+1$，但是思考之后发现，尽管 $a_{x_i}\le k,z_i\le k$，$a_{x_i}\oplus z_i$ 的值仍然可能 $> k$。

因此问题就变为：对于每个连通块，随便选一个点 $x$，你需要求出有多少个值是「合法」的，即：对于每条 $x\to p$ 的链，链上的边权异或和与 $a_x$ 的取值异或得到的值不能超过 $k$。

直接枚举 $[0,k]$ 内的所有取值，复杂度 $O(nk)$。这就是我半年前场上的做法（

实际上可以注意到，对于一个点 $p$，对于任意一条 $x\to p$ 的路径，其边权异或和必然相同；否则答案即为 $0$。

我们可以对每个点 $p$ 求出 $x\to p$ 路径上的边权异或和，然后把这些数全都放进一个 $\text{01-Trie}$ 里。

现在就相当于要求出：有多少个数，使得它与 $\text{Trie}$ 内的所有数中异或最大值不超过 $k$。

我们从根开始往下走，依次决定每一位应该选什么。

取到第 $i$ 位时记录此时异或最大值 $S$，然后讨论这一位上能否选 $0/1$：

- 如果 $S>k$，那么直接递归终止，然后 `return` 回去。

- 当前节点有两个子节点：那么不管现在取什么都必然会出现一个 $1$。因此直接令 $S$ 加上 $2^i$，往左右子树递归即可。
- 当前节点有一个子节点：那么如果在这一位上选了相同的数，$S$ 至多加上 $2^i-1$。如果 $S+2^i-1\le k$ 那么肯定可以，因此可以直接将答案加上 $2^{i-1}$，同时将 $S$ 加上 $2^i$（相当于这一位上取了相反的数），继续递归；否则这一位上必然不能取不同的值，那么直接往相同方向递归即可。
- 当前节点是叶子结点：那么如果 $S\le k$ 就返回 $1$，否则为 $0$。

这样一来，我们相当于只遍历了一次 $\text{Trie}$，总的复杂度就是 $O(n\log V)$。其中 $V=2^{30}$ 为值域。

然后就做完了。

```cpp
#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int MN=5e5+5;
const int mod=1e9+7;
int n,m,k;

struct Trie{
	int d[MN<<5][2],tot;

void clear(){
		for(int i=1;i<=tot;i++)d[i][0]=d[i][1]=0;
		tot=1;
	}

void ins(int x){
		int p=1;
		for(int i=30;i>=0;i--){
			int c=(x>>i)&1;
			if(!d[p][c])d[p][c]=++tot;
			p=d[p][c];
		}
	}

int query(int p,int S,int w){
		if(S>k)return 0;
		if(w<0)return 1;
		if(d[p][0]&&d[p][1])return (query(d[p][0],S+(1ll<<w),w-1)+query(d[p][1],S+(1ll<<w),w-1))%mod;
		else{
			int q=(d[p][0]|d[p][1]);
			if(S+(1ll<<w)-1<=k)return (query(q,S+(1ll<<w),w-1)+(1ll<<w))%mod;
			else return query(q,S,w-1);
		}
	}
}tree;

struct Edge{
	int to,cost;
	Edge(int T,int C):to(T),cost(C){}
	Edge(){}
};
vector<Edge>G[MN];
int dis[MN];
bool vis[MN];

void dfs(int u){
	vis[u]=1,tree.ins(dis[u]);
	for(auto e:G[u]){
		int v=e.to,w=e.cost;
		if(vis[v]&&(dis[v]!=(dis[u]^w))){puts("0");exit(0);}
		if(vis[v])continue;
		dis[v]=(dis[u]^w),dfs(v);
	}
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

n=read(),m=read(),k=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		G[x].push_back(Edge(y,z)),G[y].push_back(Edge(x,z));
	}

int ans=1;
	for(int i=1;i<=n;i++){
		if(!vis[i])tree.clear(),dfs(i),ans=ans*tree.query(1,0,30)%mod;
	}
	cout<<ans<<endl;

return 0;
}
```

正在渲染内容...