A. A Bit Common

确认情况的划分方法

基于与的性质，若要使得存在一个子序列的按位与为1，而1为00...001，最低位为1，其余位为0。那么：

  1. 对于低1位，至少要有一个1。否则全是0，无论怎么选取子序列，都不可能让最终结果为1。
  2. 对于其它位至少要有一个0。否则全是1，无论怎么选取子序列，都不可能让最终结果为0。

但是这样子考虑只能跑暴力枚举作为校验条件使用，而题目并不要求我们求出每一种情况的具体内容，只需要计次就行，显然是要求我们推导出简便的数学公式。

所以说需要细化我们的结论，不然不好推公式。

不妨考虑符合条件的子序列内部的情况：

  1. 低1位必须全部是1
  2. 至少要有一个数在第位为0，其中指代任意的非低1位的位

而对于子序列的外部，每一位的排布都可以是任意的

但是这样子很难不重复考虑，因为存在这种情况：

一行是一个数的二进制形式，低位在右边

0 0 0 1
1 1 1 1

既可以把两个数都看出子序列内部，也可以把其中一个数看成子序列内部，另一个数看成子序列外部。说明这样子划分无法特异区分出这两种不同的情况，显然是不行的。

我们注意到低1位较为特殊，所以说可以考虑以低1位为依据划分子序列与非子序列。

如果已有一个子序列，那么新增一个任意的最低位为1的数并不会破坏已有的子序列，所以最低位为1的数都可以看成子序列内部的元素。

推导公式

示意图

如上图，我们有个数(图中)，个二进制位(图中)。

记子序列部分的长度为，可以发现。当时，子序列内部的数为1即可。当时，只需要满足结论1即可。

我们开始考虑更一般的情况：

  1. 在子序列内部讨论：单独看某一个非低1位的一列，里面至少有一个0。那么考虑0的个数为1的情况 + 0个数为2的情况 + ... + 0个数为k的情况，即。实际上，就是随机排布的情况减一，也就是除了全是1的情况皆可。而对于整个子序列来说，非低1位一共有个，这些是同时发生的，所以说用的是乘法。这部分总的情况数为。
  2. 讨论非子序列的部分：根据前面的划分规则，非子序列为低1位为0的情况，剩余所有位都没有限制，所以说对于每一个非低1位，有种情况。非低1位有个，所以说一共的情况数为：。
  3. 子序列可以和非子序列混合，从n个数里面选取出k个数为子序列成员，有种情况。之所以不使用排列，是因为子序列内部用的公式为，实际上已经包含了排列，如果这里再用排列就重复了。

这三种情况是同时发生的，所以说乘起来就是最终的公式：

最后我们只需要用个for取遍然后累加即可：

组合数用杨辉三角递推。

虽然理论上可直接拆分为阶乘，但是在模意义下除法得用乘法逆元，需要确保要求逆元的数和q互质，而本题的q不保证是质数！所以说会错！

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e3 + 10;

// 杨辉三角求组合数
int comb[N][N];

// 模q意义下
int q;

// 预处理组合数，5000*5000=2e7不会T
void init() {
	int onemod = 1 % q;
	comb[0][0] = comb[1][0] = comb[1][1] = onemod;
	for (int i = 2; i <= 5000; i++) {
		comb[i][0] = onemod;
		comb[i][i] = onemod;
		for (int j = 1; j < i; j++) {
			comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % q;
		}
	}
}

// 模q快速幂
int qpow(int a, int b) {
	int ans = 1ll;
	for (; b; b >>= 1ll) {
		if (b & 1ll) {
			ans = (ans*a) % q;
		}
		a = (a*a) % q;
	}
	return ans;
}

signed main() {
	int n, m;
	cin >> n >> m >> q;
	init();
	int ans = 0;
	// 执行公式
	for (int k = 1; k <= n; k++) {
		// ((2^k)-1)^(m-1)
		int t = qpow(qpow(2ll, k) - 1ll, m - 1ll);
		// 2^((n-k)*(m-1))
		t = (t*qpow(2ll, (n - k) * (m - 1ll))) % q;
		// C(n,k)
		t = (t * comb[n][k]) % q;
		// 累加
		ans = (ans + t) % q;
	}
	cout << ans;
	return 0;
}