题解：P11498 [ROIR 2019 Day 1] 机器学习
ChatSheep
·
·
题解
前言
数位动态规划的成分不高，套的模板特别经典，不过作为动态规划练手不错，蓝绿差不多了。
思路
以下所说的一个数字 x 集合均为 x 在二进制下 1 的位置集合。
第一步应该要理解 (a_i \operatorname{and} a_j) = a_i 说明了什么。
根据位运算的性质，这句话的意思应该是 a_i 是 a_j 的一个位子集。
具体来说，a_i 的某一个二进制位是 1 的情况下，a_j 对应的二进制位也一定是 1。
由于子集这个运算具有传递性，所以只需要满足 $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](/problem/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)$，参考某一篇题解应该是可以继续优化的，但是轻微卡常足以通过。
## 代码
注意，代码中的转移顺序是完全颠倒的，仅供参考。
```cpp
#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;
}
```