A bit Common

题目大意和思路可以看这篇帖子里的资料：https://ac.nowcoder.com/discuss/1295959?type=101&order=0&pos=2&page=1&channel=-1&source_id=1

思路

个人对ppt中的公式理解如下： alt
没钱充会员去不掉水印

假设n为4，m为4，任意一种排列情况可能如上图。要使得这组排列有非空子排列的AND和为1，有几个条件

  • 这个排列里必定有至少一个以上的数字末位为。假设为个，这里有种情况

  • 对于末位为1的数字，每一位都至少有一个。这里有（所有的可能为，减去一种该位个都是的情况），总共位需要选择是0还是1，一共

  • 对于末位为的数字，每一位是还是随便，这里有，总共总共位需要选择是0还是1，一共

上述所有情况需要同时满足，所有的情况数相乘，在对k从1到n求和，得到n个中k个末位为1，含AND和为1的子集的序列个数公式：

关键点就在于求幂、求组合数，用快速幂求大指数幂，用杨辉三角递推组合数。

代码实现

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, m, q;
ll comnum[5005][5005]; // 杨辉三角递推求组合数

ll fastPow(ll a, ll b, ll q) {
	ll res = 1 % q;
	while(b) {
		if(b & 1) res = (res * a) % q;
		a = (a * a) % q;
		b >>= 1;
	}

	return res;
} // 快速幂

inline ll comb(ll n, ll m) {
	return comnum[n][m] ;
}

int main() {
	cin >> n >> m >> q;
	ll sum = 0;

	comnum[1][1] = 1;

	for(int i = 0; i <= 5001; i ++ ) {
		comnum[i][i] = 1;
		comnum[i][0] = 1;
	}

	for(int i = 1; i <= 5001; i ++ ) {
		for(int j = 1; j <= i; j ++ ) {
			comnum[i][j] = (comnum[i - 1][j - 1] % q + comnum[i - 1][j] % q) % q;
		}
	}
	// 求组合数

	for(int k = 1; k <= n; k ++ ) {
		sum = (sum + (fastPow(fastPow(2, k, q) - 1, m - 1, q) % q * comb(n, k) % q * fastPow(fastPow(2, (n - k), q), (m - 1), q)) % q) % q;
	} // 公式k从1到n累加

	cout << sum << endl;
}

之前同余关系一直没弄清楚，补题的时候也一直溢出，最后干脆所有能加取模的地方都加上终于过了