Fork me on GitHub

qbxt D2T2 Code 题解

看了一眼之后完全就是一脸懵逼的题….

首先先读题$qaq$…..
题目的大致意思就是给你一个矩阵,然后问你把这个矩阵横竖填成异或值为$1$的矩阵的方案数。

很明显,这道题没有什么枚举上界,所以你想直接枚举的话是不太可能的。
那么我们怎么办呢$?$

我也不知道

既然枚举补星,那么我们就用一个比较常见的正难则反的思想。
对于这道题,我们可以容斥的去做

那么,首先,所有的方案是什么呢?

为什么呢?
一共有n+m个校验码,我们按位数考虑,在只有1位的情况下,那么这一位可能是$0$或者$1$。
那么就是$(2^n)^m$的方案数了。

然后我们考虑对于每一位删掉不合法的情况:
因为异或起来是$1$,那么对于没一行或者每一列,$1$的个数总是奇数。
那么我们就可以根据这个东西来进行删除不合法状态的操作了

最后统计出来答案

我们发现,因为有$k$位,而我们是按位考虑的。
所以我们最后要取答案的$k$次方。

代码如下:

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
#include <bits/stdc++.h>
#define int long long

const int N = 505;
const int MOD = 1e9 + 7;

int c[N][N];
int n , m , k , t , ans;

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

int Fast_Power ( int x , int y ) {
int sum = 1;
while ( y ) {
if ( y & 1 )
sum = sum * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return sum;
}

signed main() {
for ( int i = 1 ; i <= 500 ; i++ )
c[i][i] = c[i][0]=1;
for ( int i = 2 ; i <= 500 ; i++ )
for ( int j = 1 ; j < i ; j++ )
c[i][j] = ( c[i - 1][j] + c[i - 1][j - 1] ) %MOD;
t = read();
while ( t-- ) {
n = read () , m = read() , k = read ();
int ans = Fast_Power ( 2 , n * m );
for ( int i = 0 ; i <= n ; i++ )
for ( int j = 0 ; j <= m ; j++ ) {
if ( i == 0 && j == 0 )
continue;
if ( ( i + j ) & 1 )
ans = ( ans + MOD - Fast_Power ( 2 , ( n - i ) * ( m - j ) ) * c[n][i] % MOD * c[m][j] % MOD ) % MOD;
else
ans = ( ans + Fast_Power ( 2 , ( n - i ) * ( m - j ) ) * c[n][i] % MOD * c[m][j] % MOD ) % MOD;
}
ans = Fast_Power ( ans , k );
printf ( "%lld\n" , ans );
}
return 0;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:qbxt D2T2 Code 题解

文章作者:兮水XiShui丶

发布时间:2018年11月04日 - 10:11

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.top/2018/11/04/题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。