[DS记录]P7717 「EZEC-10」序列

**题意** ： 求有多少个不同的长为 $n$ 的序列 $A$，满足： 2. $A\subseteq [0,k]∩\rm Z$ 3. 满足 $m$ 组形如 $(x_i,y_i,z_i)$ 的限制，每组限制的意义为 $A_{x_i} {\ \rm xor\ } A_{y_i} = z_i$。 答案对 $10^9+7$ 取模。 $n,m\leq 5\times 10^5$ ，时限 $\texttt{1s}$ ，空限$\texttt{512M}$。 ------------ 将限制看做无向边，对每个联通块分别做，答案相乘。 找出一颗生成树，可以将 $A$ 的自由度消至 $1$ ，且显然不能再更小。 对于非树边，检查一下是否符合，若不符合直接输出 $0$。 记 $S_i$ 为 $A_1{\ \rm xor\ }A_i$ 的值，考虑 $A_1$ 的可能取值。 问题转化为 ： - 有 $m$ 条限制 $x{\ \rm xor\ y_i}\leq k$ ，问 $x$ 的可能取值数。 用 $\rm 01Trie$ 刻画每个不等式的解集，为每个解集 $+1$ ，最后计算 $m$ 的个数。 时空复杂度 $O\big((n+m)\log n\big)$。 ```cpp ```