问题本质

构造数组 $[a_1, a_2, ..., a_n]$，满足：

1. $0 \leq a_i \leq k$
2. 对任意 $i < j$，$(a_i \operatorname{and} a_j) = a_i$（按位包含）
3. $m$ 个不等约束 $a_{l_i} \neq a_{r_i}$

核心洞察

关键性质

条件 $(a_i \operatorname{and} a_j) = a_i$ 意味着：

• 所有 $a_i$ 的二进制位构成嵌套关系
• 存在一个最大数 $M$，其他所有数都是 $M$ 的二进制子集

算法步骤

1. 确定候选值集合

• 找出所有满足 $x \subseteq k$ 的数（$x$ 的二进制位是 $k$ 的子集）
• 设候选值数量为 $C$

2. 处理约束条件

• 将不等约束视为图中的边
• 找出所有连通分量
• 每个连通分量内的值必须互不相同

3. 组合计数

对于每个连通分量：

• 大小为 $s$ 的分量有 $P(C, s) = C \cdot (C-1) \cdots (C-s+1)$ 种赋值方式

总方案数 = 所有连通分量方案数的乘积

特殊情况

• $m = 0$：方案数 = $C^n$（每个位置独立选择）
• 存在大连通分量：如果某个 $s > C$，答案为 $0$

复杂度

• 候选值计算：$O(\log k)$
• 图遍历：$O(n + m)$
• 总复杂度：$O(n + m + \log k)$

实现要点

1. 使用 DFS 或并查集找连通分量
2. 模 $10^9+7$ 运算
3. 预处理阶乘用于排列计算

这种解法将复杂的位运算约束转化为图论问题，通过连通分量分析高效计数。