题目大意

给定两个正整数 和 ，求满足以条件的长度为 的数列 有多少个：

• ，；
• 存在非空子序列 ，使得其按位与之和为 。

前置知识

不是很难的一道题，难度在橙~黄左右，算法小奥组合数和加乘原理。

解法

• 看到这种计数题，自然想组合计数。先分析一下数列 什么时候可以满足按位与之和为 。显然，将每个数拆成二进制位（ 位），以下两个条件均满足时即成立：

1. 对于第 位（，以下简称末位），所有数都是 ；
2. 对于第 （） 到 （） 位，所有数中至少有一个数这一位是 。

• 显然，直接正着做会比较难做，于是考虑重要计数思想正难则反。正难则反，顾名思义，就是算出有多少种情况不满足条件，然后从总情况数 中减去即可。

• 对于第一个条件，不满足它显然就是第末位全为 ，选不出来一个子序列，第 位固定，其他随意，总共 种；

• 然后考虑末位有 的情况，考虑 到 枚举有 个数末位不为 。这里说一下，由于数据范围 ，所以考虑平方级别的算法。考虑当有 个数末位不为 时对答案的贡献是多少。由于是数列，所以选哪 个数有 种情况。另外 个数除末位（为 ）外都随意，。对答案的贡献就是 ，这里， 的意思是求对于长度为 的数列 有多少个，使得其末位都为 ，且其它位中至少有一位，其对于所有 这一位上都为 （有点绕，可以多读几遍），简而言之就是虽然末位是 但按位与起来和不是 。

• 考虑如何计算 。为了避免重复计数，显然可以先 到 枚举有多少位全为 （设其为 ）。 位中选出 位，，这 位都是固定的（全为 ），考虑其它 位。显然，要求对于每一位都至少有一个 ，正着做不好做，再次正难则反，每一位 个数，由有 位，所以 种，对于所有的 ，加起来即可。

• 然后就做完了，时间复杂度 。由于要取模，常数较大，可能会被卡，所以考虑预处理 和 的幂次，总体时间复杂度优化至 量级。

code

最后放一下赛时代码（马蜂奇特，如有不适请见谅）：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NR = 5000;
int n, m, MOD, ans, c[NR + 1][NR + 1], p[NR * NR + 1], s[NR + 1][NR + 1];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> MOD;
	int MAXN = max(n, m);
	p[0] = 1;
	for (int i = 1; i <= MAXN * MAXN; i++)
		p[i] = p[i - 1] * 2 % MOD;
	ans = p[n * m];
	for (int i = 0; i <= MAXN; i++){
		for (int j = 0; j <= i; j++){
			if (!j) 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++){
		int base = ((p[i] - 1) % MOD + MOD) % MOD;
		s[i][0] = 1;
		for (int j = 1; j <= m - 2; j++)
			s[i][j] = s[i][j - 1] * base % MOD;
	}
	ans = ((ans - p[n * (m - 1)]) % MOD + MOD) % MOD;
	for (int j = 1; j <= n; j++){
		int cur = c[n][j] * p[(n - j) * (m - 1)] % MOD;
		int now = 0;
		for (int k = 1; k <= m - 1; k++){
			int t = s[j][m - 1 - k];
			t = t * c[m - 1][k] % MOD;
			now = (now + t) % MOD;
		}
		cur = cur * now % MOD;
		ans = ((ans - cur) % MOD + MOD) % MOD;
	}
	cout << ans << endl;
	return 0;
}

THE END