# 五校联考模拟赛Day2T2矩阵(容斥原理)

## 题意

$n * m$的网格，对其进行黑白染色，问每一行每一列至少有一个黑格子的方案数。

## Sol

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
#include<iostream>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long
#define LL long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M;
LL fac[MAXN], ifac[MAXN], po2[MAXN];
LL fastpow(int a, int p) {
LL base = 1;
while(p) {
if(p & 1) base = (base * a) % mod;
a = (a * a) % mod; p >>= 1;
}
return base % mod;
}
LL C(int N, int M) {
return fac[N] * ifac[M] % mod * ifac[N - M] % mod;
}
main() {
N = 2 * 1e5;
fac[0] = 1; po2[0] = 1;
for(int i = 1; i <= N; i++) fac[i] = i * fac[i - 1] % mod, po2[i] = (po2[i - 1] * 2) % mod;
ifac[N] = fastpow(fac[N], mod - 2);
for(int i = N; i >= 1; i--)
ifac[i - 1] = (ifac[i] % mod * i) % mod;
int d = 1; LL ans = 0;
for(int i = 0; i <= N; i++, d *= -1)
ans = (ans + d * C(N, i) * fastpow((po2[N - i] - 1 + mod) % mod, M) % mod + mod) % mod;
cout << ans;
return 0;
}

1811 篇文章114 人订阅

0 条评论

## 相关文章

2517

2422

36412

1393

3579

3676

### PHP取余的那些事

1、百分号取余 $val=9.45;$result=$val*100; echo intval($result); //这里输出944 echo \$re...

36710

3576

1763

994