校验码

题面

题目背景

Wwq 为了能破解室友的 QQ 密码特地选修了信科密码学的课。然后，他终于在开学一个月后意识到这个课好像和他想象的完全不一样。

今天老师上课介绍了校验码。校验码的作用之一是检查数据在传输过程中是否出错，其历史可以追溯到犹太人写圣经。

聪明的希伯来人在誊写圣经的时候为了保证绝对正确，除了提醒自己要仔细和反复检查外，他们还采取了一种特殊的方法——他们给希伯来字母编了码，这样圣经的每一行都是一串数字，他们把这串数字经过一定的运算后得到一个数字，再转化回希伯来字母。

这样圣经的单独每一行都有一个校验字母，每一列也有一个校验字母，他们只要在誊写完一页圣经后立刻对比所有的校验字母是否和原圣经相同即可。（我们一般认为在同一行犯错两次的概率比较低）

题目描述

Wwq 被这种简单而有效的数学美打动了，他决定也用这种方法来生成他昨晚做题时得到的一个矩阵的校验码。（虽然我们根本不知道 Wwq 生成校验码能做什么，也许是单纯为了好玩）

为了处理 Wwq 最头疼的溢出问题，Wwq 在计算校验码时直接使用了位运算 \(|(or)\)，这样他处理任何数都不用考虑溢出的问题了。

也就是说，Wwq 现在有一个 \(N \times M\) 的矩阵，矩阵中每个数都是一个 K 位 2 进制数，Wwq 会把矩阵每一行的数都或起来，得到 N 个数，他也会把每一列的数都或起来，得到 M 个数，这样他就有了 \(N + M\)个校验码。

然后——Wwq 发现他的矩阵在计算后得到的 \(N+M\) 个校验码全是 \(2^k - 1\) ……

Wwq 现在有了个新问题，有多少种不同的情况会导致得到的校验码全是 \(2^k-1\) 呢？

即，有多少个 \(N \times M\) 的矩阵满足：其所有数字都是 K 位 2 进制数，且每一行每一列的或都是 \(2^k - 1\)。

输入格式

多组测试数据，在输入的第一行会给出测试数据组数 T 。

每组测试数据一共一行，为三个整数 N,M,K 。

输出格式

输出每组数据一行，即答案。

样例输入

样例输出

提示&说明

对于 \(30\%\) 的数据，N,M 不超过 10。

对于 \(100\%\) 的数据， N,M 不超过 50 , K 不超过 31。

题解

因为二进制下的位与位之间没有关系，因此我们可以先考虑 k = 1 时的情况。

我们把行和列分开来考虑，看每一行，答案的情况就有 \(2^n\) 种，因为有一种都是零的情况不合题意，因此每一行的答案就是， \(2^n - 1\)，又因为有 m 行，所以答案就是 \((2^n-1 )^m\) ，然后你感觉这个东西有点不对，好像算重了一部分，然后你会发现还要乘上一个容斥系数。

然后就是 \(\displaystyle ans = \sum_{i = 0} ^n (-1)^i{n \choose i} (2^i-1)^m\)

这个是 k=1 的时候的答案，最后的时候 \(ans ^k\)就行了.

code

#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define M 60

using namespace std;
const int mod = 1e9+7;
ll n, m, k, C[M][M];

ll read() {
	ll s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

ll q_pow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return ans;
}

ll F(ll x) {
	return q_pow((q_pow(2,x) - 1),m);
}

void get_c() {
	for (int i = 0; i <= 50; i++) C[i][0] = 1;
	for (int i = 1; i <= 50; i++)
		for (int j = 1; j <= i; j++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}

int main() {
	freopen("code.in", "r", stdin);
	freopen("code.out", "w", stdout);
	get_c();
	int T = read();
	while (T--) {
		n = read(), m = read(), k = read();
		if (n > m) swap(n, m);
		ll ans = 0;
		for (ll i = 0; i <= n; i++) {
			ll b = 1;
			if (i & 1) b = -1;
			ans = (ans + (C[n][i] * F(n - i) * b % mod + mod) % mod) % mod;
		}
		printf("%lld\n", q_pow(ans, k));
	}
	return 0;
}

校验码