A Bit More Common (2024牛客多校1 B)

进入博客阅读体验更佳：A Bit More Common (2024牛客多校1 B) | 付诺の小站 (funuo0728.github.io)

A Bit More Common

题目大意

给定两个整数n和m(1 \le n,m \le 5000)，在所有长度为n且元素取值范围为[0, 2 ^ m)的序列中，计算存在两个合法子序列的序列个数。其中，合法子序列是指子序列中所有元素按位与的结果为1。

由于答案可能很大，请将其对q(1 \le q \le 10^9)取模。

解题思路

首先考虑至少存在一个合法子序列的序列个数，对于合法子序列中的元素，第0位必须全为1，其余位上至少有一个0，对于剩下的其他元素，第0位必须全为0，其余位任选。我们对序列长度进行枚举，最终得到：

\sum_{i = 1}^{n}C_{n}^{i}(2 ^ {i} - 1)^{m - 1}2^{(m - 1)(n-i)} ①

题目要求我们求至少存在两个合法子序列的序列个数，那么接下来只需要求恰好只有一个合法子序列的情况，最后用至少1个的方案数减去恰好1个的方案数即为所求结果。

考虑这样一种按位与为1的子序列，去掉其中任何一个元素，他们的按位与都会变得不为1。首先这些元素的第0位上肯定都为1，自然想到如果某一个数在某一位上为0，而其余数在这一位上都为1，那么这个数就是不可或缺的。姑且将这种有且只有一个数在这一位上为0的位称为特殊位，只要每一个数都至少对应一位特殊位，这样得到的子序列就是要求的子序列。

考虑二维dp，f[i][j]表示总共有i个数，j位特殊位，每个数至少对应一个特殊位的方案数。

对于f[i][j]来说，每加入一位特殊位，可以使i个数字中的其中一个对应它，共有i种情况；也可以新增一个数字来对应它，然后发现从f[i][j]到f[i +1][j + 1]难以确定转移方程，于是思考从f[i + 1][j + 1]到f[i][j]，发现去掉一个特殊位并使数减少的情况共有i + 1种，最终可得转移方程：

f[i][j] = i\cdot f[i][j - 1] + i\cdot f[i - 1][j - 1]

那么恰好存在一个合法子序列的思考方式与至少存在一个类似：

首先确定子序列的长度i，取长度为i的子序列的方案数为C_{n}^{i}，

第0位全部为1，每个数至少对应1个特殊位，那么现在确定特殊位的个数j，至少为i，至多为m - 1，取j个特殊位的方案数为C_{m -1}^{j}，

这i个数对应j个特殊位的方案数位f[i][j]，

对于除去第0位和特殊位的其他位，每一位的总方案数为2 ^ i，减去全为1的情况为2 ^ i -1，再减去使这一位成为特殊位的情况2 ^ i - i - 1，最后这样的位有m - 1 - j个，那么方案数为(2^i - i - 1) ^ {m-1-j}，

最后考虑其余数字，对于这些数字来说，除了第0位，其余位任填，方案数位2 ^ {(m - 1)(n-i)}，

最终方案数为：

\sum_{i = 1}^{n}2^{(m - 1)(n - i)}C_n^i\cdot\sum_{j=i}^{m-1}C_{m-1}^jf[i][j](2^i - i - 1) ^ {m-1-j} ②

最后用①式减去②式即可。

参考代码

#include <bits/stdc++.h>
#define maxn 5010
#define int long long
using namespace std;
const double eps = 1e-8;
typedef long long ll;
typedef __int128_t i128;
i128 _base=1;
​
int n, m, mod, res = 0;
int C[maxn][maxn], f[maxn][maxn], pow2[maxn], tt[maxn];
​
inline ll mol(ll x){return x-mod*(_base*x>>64);}
​
int qmi(int a, int b, int m) {
    int res = 1;  a = mol(a);
    while(b) {
        if(b & 1)  res = mol(res * a);
        a = mol(a * a);
        b >>= 1;
    }
    return res;
}
​
void solve() {
    cin >> n >> m >> mod;
​
    _base=(_base<<64)/mod;
​
    pow2[0] = 1;
    for (int i = 1; i <= n; ++i)  pow2[i] = pow2[i - 1] * 2 % mod;
    for (int i = 1; i <= n; ++i)  tt[i] = qmi(2, (m - 1) * (n - i), mod);
 
    for (int i = 0; i <= 5000; ++i) {
        for (int j = 0; j <= i; ++j) {
            if(j == 0)  C[i][j] = 1;
            else  C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
 
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= m - 1; ++j) {
            if(i == 1)  f[i][j] = 1;
            else  f[i][j] = i * (f[i][j - 1] + f[i - 1][j - 1]) % mod;
        }
    }
 
    for (int i = 1; i <= n; ++i) {
        int t1 = C[n][i] * qmi((pow2[i] + mod - 1) % mod, m - 1, mod) % mod * tt[i] % mod;
        res = (res + t1) % mod;
    }
 
    res = ((res - C[n][1] * qmi(2, (n - 1) * (m - 1), mod) % mod) % mod + mod) % mod;
 
    for (int i = 2; i <= n; ++i) {
        for (int j = i; j <= m - 1; ++j) {
            int t1 = C[n][i] * tt[i] % mod;
            int t2 = C[m - 1][j] * f[i][j] % mod * qmi(((pow2[i] - i - 1) % mod + mod) % mod, m - 1 - j, mod) % mod;
            res = ((res - (t1 * t2 % mod)) % mod + mod) % mod;
        }
    }
​
    cout << res << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}