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

题意

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

Sol

考场上只会$n^3$的dp,还和指数级枚举一个分qwq

设$f[i][j]$表示到了第$i$行,已经有$j$列被染黑,然后暴力转移上一行有几个黑格子

正解是容斥

首先固定好列,也就是保证每一列都有一个黑格子

这样的方案是$(2^N - 1) ^M$

然后容斥行

组合数暴力算即可

#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;
inline int read() {
    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;
    N = read(); M = read();
    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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青玉伏案

算法与数据结构(五) 普利姆与克鲁斯卡尔的最小生成树(Swift版)

上篇博客我们聊了图的物理存储结构邻接矩阵和邻接链表,然后在此基础上给出了图的深度优先搜索和广度优先搜索。本篇博客就在上一篇博客的基础上进行延伸,也是关于图的。今...

2517
来自专栏进击的程序猿

seq2seq模型之raw_rnn

本文是seq2seq模型的第二篇,主要是通过raw_rnn来实现seq2seq模型。 github地址是:https://github.com/zhuanxu...

2422
来自专栏小樱的经验随笔

Vijos P1116 一元三次方程求解【多解,暴力,二分】

一元三次方程求解 描述 有形如:ax^3+bx^2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三...

36412
来自专栏mathor

枚举+优化(5)——双指针优化1

1393
来自专栏专注数据中心高性能网络技术研发

HERD--位运算

判断一个数是否是2的次方 1 static inline int hrd_is_power_of_2(uint32_t n) 2 { 3 retur...

3579
来自专栏深度学习之tensorflow实战篇

tensorflow(一)windows 10 64位安装tensorflow1.4与基本概念解读tf.global_variables_initializer

一.安装 目前用了tensorflow、deeplearning4j两个深度学习框架, tensorflow 之前一直支持到python 3.5,目前以更新...

3676
来自专栏我的博客

PHP取余的那些事

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

36710
来自专栏人工智能LeadAI

Python 设计模式初探

本文章是在阅读精通Python设计模式(中文版)(https://book.douban.com/subject/26829015/),以及阅读 Mask R-...

3576
来自专栏Petrichor的专栏

tensorflow编程: Neural Network

对 features 和 tf.negative(features) 分别 Relu 并 concatenate 在一起。

1763
来自专栏简书专栏

基于tensorflow的一元一次方程回归预测

安装tensorflow命令:pip install tensorflow 下面一段代码能够成功运行,则说明安装tensorflow环境成功。

994

扫码关注云+社区