题目大意
给定两个整数$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} $ $②$
最后用$①$式减去$②$式即可。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #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;
}
|
