CF1829H Don't Blame Me题解

SunnyYuan的博客 / 2023-05-14 / 原文

题意：

给定一个长度为 \(n\) 的数组，选择它的一个子序列（不一定要连续的），问有多少种选法使得它们 AND 的值的二进制表示法中有 \(k\) 个 \(1\)。

思路：

这个题就是一个简单的 DP，

设 \(f_{i,j}\) 表示选择到了第 \(i\) 个数字（但不一定是把前 \(i\) 个数字都选择了），所有被选择的数字的 AND 值等于 \(j\) 的方案数。

那么我可以不选择这个数字：\(f_{i,j} = f_{i,j} + f_{i-1,j}\)，即与选择 \(i - 1\) 个数字，数字的 AND 的值为 \(j\) 的方案数一样。

那么我们也可以选择这个数字：\(f_{i,j\& a_i} = f_{i,j\& a_i} + f_{i - 1,j}\)，即从前 \(i - 1\) 个数得到的 \(j\) 与上一个 \(a_i\) 就有前 \(i\) 个数字得到的 \(j\&a_i\)。

当然，我们为什么一定要让第 \(i\) 个数字受到前面的数字的影响呢？我们可以另起炉灶！即 \(f_{i, a_i}=1\)。

这就讨论完了所有情况。

归纳总结起来就是

\[\begin{cases} f_{i,j} = f_{i,j} + f_{i-1,j} \\ f_{i,j\& a_i} = f_{i,j\& a_i} + f_{i - 1,j} \\ f_{i, a_i}=1 \\ \end{cases} \]

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 200010, mod = 1e9 + 7;

int f[N][64];
int n, k;
int a[N];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) memset(f[i], 0, sizeof(f[i]));
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i][a[i]] = 1;
        for (int j = 0; j < 64; j++) {
            f[i][j] = (1ll * f[i][j] + f[i - 1][j]) % mod;
            f[i][j & a[i]] = (1ll * f[i][j & a[i]] + f[i - 1][j]) % mod;
        }
    }
    int res = 0;
    for (int i = 0; i < 64; i++) {
        int cnt = 0;
        for (int j = 0; j < 6; j++) {
            if (i >> j & 1) cnt++;
        }
        if (cnt == k) res = (1ll * res + f[n][i]) % mod;
    }
    cout << res << '\n';
}

int main() {
    #ifdef DEBUG
    freopen("Test.in", "r", stdin);
    cout << "===================START===================" << endl;
    #endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();

    #ifdef DEBUG
    cout << "====================END====================" << endl;
    #endif
    return 0;
}