自动搬运

查看原文

来自洛谷，原作者为

	CuteChat **

搬运于2025-08-24 23:07:52，当前版本为作者最后更新于2025-01-03 17:09:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

数位动态规划的成分不高，套的模板特别经典，不过作为动态规划练手不错，蓝绿差不多了。

思路

以下所说的一个数字 $x$ 集合均为 $x$ 在二进制下 $1$ 的位置集合。

第一步应该要理解 $(a_i \operatorname{and} a_j) = a_i$ 说明了什么。

根据位运算的性质，这句话的意思应该是 $a_i$ 是 $a_j$ 的一个位子集。

具体来说，$a_i$ 的某一个二进制位是 $1$ 的情况下，$a_j$ 对应的二进制位也一定是 $1$。

$0$ 的位置不需要管，因为这个是按位与运算。

由于子集这个运算具有传递性，所以只需要满足 $a_i$ 是 $a_{i+1}$ 的一个位子集即可，并且不难发现 $a_i \le a_{i+1}$ 恒成立。

不过这种情况并不适合我们进行状态设计，因为还有一个限制，也就是 $0\le a_i\le k$。

由不等式性质，显然 $a_n \le k$ 即可，所以就有一个初步的想法就是枚举最后一个数字。

然后就会发现，对于其他的数字，就不需要关心这个数字具体是多少了，因为无论前面的数字怎样，只要是位子集，就一定是满足这个条件的。

因此只需要关心这个集合的大小即可，具体来说，在枚举最后一个数字后，问题被转换成了如下形式：

求解所有满足条件的序列 $b$ 的贡献和：

• $0\le b_i \le b_{i+1}$。
• $b_n$ 是一个给定的值（不超过 $60$）。
• $b_{l_i} \neq b_{r_i}$。

$b_i$ 的定义就是 $a_i$ 的二进制下 $1$ 的个数，也就是集合大小。

而一个序列 $b$ 的贡献则是 $\displaystyle\prod_{i=1}^{n-1} C_{b_{i+1}}^{b_{i}}$，$C_{b_{i+1}}^{b_{i}}$ 的含义是显然的，从 $a_{i+1}$ 这个集合选出 $b_i$ 作为新的 $a_i$。

接着又注意到 $a_n$ 的值具体是多少是不关心的，同样只需要关心 $b_n$ 即可，换言之，枚举 $b_n$，统计出有多少个数字 $x$ 满足这个数字的集合大小是 $b_n$ 即可。

这个东西显然可以数位动态规划解决，不过由于数位动态规划似乎不是本题的重点，因此不细说，如有需要可以参考 P8764。

所以到这里就把问题转换成了一个很有前途的模型！

注意到 $b_i$ 不超过 $60$，所以在这个很长的序列里面，肯定很多很多段就是相同的，就像这样：

$$b=(0,0,1,1,1,2,2,2,3,3,3,4,4)$$

因此设计的动态规划就没有必要去一个一个做转移，你可以跳着转。

具体如何呢？不考虑 $m\neq 0$，则状态转移类似于这个样子：

$$dp_{i,j}=\sum_{p=0}^{i-1}\sum_{k=0}^{j-1}dp_{p,k}\times C_{j}^{k} $$

其中 $dp_{i,j}$ 表示强制钦定 $b_{i}=j$ 的时候，有多少种方案。

先不考虑优化，考虑 $m\neq 0$ 的时候怎么办，这时就会发现，只有一组限制 $(l, r)$ 满足 $l>p,r\le i$ 的时候（也就是作为闭区间时被完全包含），这个条件才会被破坏。

因此维护条件三也是简单的，只要 $[p+1,i]$ 这个转移的区间不会包含给定限制的一个二元组即可。

显然的，$p$ 的转移一定是一个区间，而且也是很好处理出这个区间的。

于是前缀和优化即可。

总体思路

通过对于按位与运算的分析可以将问题转换成如下：

求解所有满足条件的序列 $b$ 的贡献和：

• $0\le b_i \le b_{i+1}$。
• $b_n$ 是一个给定的值（不超过 $60$）。
• $b_{l_i} \neq b_{r_i}$。

然后贡献的计算是一个数位动态规划还有一堆组合数相乘。

于是再根据值域小的性质，发现最终序列一定是一段一段的，所以就决策下一个不同的位置在哪里（其实不论值域都应该想到这一点）。

最后发现只要区间没有包含关系就是合法的，而这个条件的转移上，一定是一段区间，前缀和优化即可。

时间复杂度 $O(n \log^2 k)$，参考某一篇题解应该是可以继续优化的，但是轻微卡常足以通过。

代码

注意，代码中的转移顺序是完全颠倒的，仅供参考。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int p = 1e9 + 7;
int n, m, k, dp2[64][2][64], frc[64], inv[64], cans[64], C[64][64];
signed dp1[300005][64], sum[300005][64];
int togo[300005];
int l[300005], r[300005];
vector<int> qj[300005];

int dfs2(int i, int lim, int cnt) { // 数位 DP
	if (i == -1) {
		return cans[cnt];
	}
	if (dp2[i][lim][cnt] != -1) return dp2[i][lim][cnt];
	int ans = 0;
	for (int j = 0; j <= max(lim, ((k >> i) & 1)); ++j) {
		ans += dfs2(i - 1, lim || (j != ((k >> i) & 1)), cnt + j);
	}
	return dp2[i][lim][cnt] = ans % p;
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= m; ++i) {
		cin >> l[i] >> r[i];
		if (l[i] > r[i]) swap(l[i], r[i]);
		qj[l[i]].push_back(r[i]);
	}
	inv[0] = frc[0] = inv[1] = frc[1] = 1;
	for (int i = 2; i <= 63; ++i) {
		frc[i] = frc[i - 1] * i % p;
		inv[i] = (p - p / i) * inv[p % i] % p;
	}
	for (int i = 2; i <= 63; ++i) (inv[i] *= inv[i - 1]) %= p;
	int mn = 1ll << 60;
	for (int i = n; i >= 1; --i) {
		for (auto j : qj[i]) mn = min(mn, j);
		togo[i] = mn;
	}
	memset(dp2, 255, sizeof(dp2));
	C[0][0] = 1;
	for (int i = 1; i <= 62; ++i) {
		for (int j = 0; j <= 62; ++j) {
			C[i][j] = (C[i - 1][j] + (j ? C[i - 1][j - 1] : 0)) % p;
		}
	}
	for (int i = n; i >= 1; --i) {
		for (int cnt = 0; cnt <= 60; ++cnt) {
			if (i == n) {
				dp1[i][cnt] = 1;
				continue;
			}
			int ans = 0;
			if (togo[i] > n) {
				for (int k = 0; k <= cnt; ++k) (ans += C[cnt][k] * dp1[i + 1][k]) %= p;
			} else {
				for (int k = 0; k < cnt; ++k) {
					(ans += C[cnt][k] * (sum[i + 1][k] - sum[togo[i] + 1][k]) % p) %= p;
				}
			}
			dp1[i][cnt] = ans % p;
		}
		for (int cnt = 0; cnt <= 60; ++cnt) sum[i][cnt] = (sum[i + 1][cnt] + dp1[i][cnt]) % p;
	}
	for (int i = 0; i <= 60; ++i) {
		cans[i] = (dp1[1][i] % p + p) % p;
	}
	cout << dfs2(60, 0, 0) << "\n";
	return 0;
}