BZOJ4487 [Jsoi2015]染色问题
题目描述
题目分析
发现三个限制,大力容斥推出式子是\(\sum_{i=0}^{N}\sum_{j=0}^{M}\sum_{k=0}^{C}(-1)^{N+M+C-i-j-k}*(k+1)^{i*j}*\binom{N}{i}*\binom{M}{j}*\binom{C}{k}\)
由于数据范围较小,支持\(O(nmC)\)的做法。直接暴力预处理幂和组合数,暴力计算即可。
是代码呢
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mo=1e9+7;
ll C[405][405],n,m,c,ans;
int p[405][160002];
int main()
{
cin>>n>>m>>c;
C[0][0]=1;
for(int i=1;i<=max(n,max(m,c));i++){
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
}
}
for(int i=1;i<=c+1;i++){
p[i][0]=1;
for(int j=1;j<=n*m;j++){
ll t=1ll*i*p[i][j-1]%mo;
p[i][j]=t;
}
}
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=c;k++){
(ans+=1ll*C[n][i]*C[m][j]%mo*C[c][k]%mo*p[k+1][i*j]%mo*((n+m+c-i-j-k)%2==0?1:-1))%=mo;
}
ans=(ans+mo)%mo;
cout<<ans;
}
BZOJ4487 [Jsoi2015]染色问题的更多相关文章
-
[bzoj4487][Jsoi2015]染色_容斥原理
染色 bzoj-4487 Jsoi-2015 题目大意:给你一个n*m的方格图,在格子上染色.有c中颜色可以选择,也可以选择不染.求满足条件的方案数,使得:每一行每一列都至少有一个格子被染色,且所有的 ...
-
bzoj4487[Jsoi2015]染色问题 容斥+组合
4487: [Jsoi2015]染色问题 Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 211 Solved: 127[Submit][Status ...
-
2019.02.09 bzoj4487: [Jsoi2015]染色问题(容斥原理)
传送门 题意简述: 用ccc中颜色给一个n∗mn*mn∗m的方格染色,每个格子可涂可不涂,问最后每行每列都涂过色且ccc中颜色都出现过的方案数. 思路: 令fi,j,kf_{i,j,k}fi,j,k ...
-
[BZOJ4487][JSOI2015]染色问题(容斥)
一开始写了7个DP方程,然后意识到这种DP应该都会有一个通式. 三个条件:有色行数为n,有色列数为m,颜色数p,三维容斥原理仍然成立. 于是就是求:$\sum_{i=0}^{n}\sum_{j=0}^ ...
-
BZOJ4487 JSOI2015染色问题(组合数学+容斥原理)
逐个去除限制.第四个限制显然可以容斥,即染恰好c种颜色的方案数=染至多c种颜色的方案数-染至多c-1种颜色的方案数+染至多c-2种颜色的方案数…… 然后是限制二.同样可以容斥,即恰好选n行的方案数=至 ...
-
【BZOJ4487】[JSOI2015]染色问题(容斥)
[BZOJ4487][JSOI2015]染色问题(容斥) 题面 BZOJ 题解 看起来是一个比较显然的题目? 首先枚举一下至少有多少种颜色没有被用到过,然后考虑用至多\(k\)种颜色染色的方案数. 那 ...
-
【bzoj4487】[Jsoi2015]染色问题 容斥原理
题目描述 棋盘是一个n×m的矩形,分成n行m列共n*m个小方格.现在萌萌和南南有C种不同颜色的颜料,他们希望把棋盘用这些颜料染色,并满足以下规定: 1. 棋盘的每一个小方格既可以染色(染成C种颜色中 ...
-
【BZOJ4487】[JSOI2015] 染色问题(高维容斥)
点此看题面 大致题意: 有一个\(n*m\)的矩形,先让你用\(C\)种颜色给它染色.每个格子可染色可不染色,但要求每行每列至少有一个小方格被染色,且每种颜色至少出现一次.求方案数. 高维容斥 显然题 ...
-
【题解】JSOI2015染色问题
好像这个容斥还是明显的.一共有三个要求,可以用组合数先满足一个,再用容斥解决剩下的两个维.(反正这题数据范围这么小,随便乱搞都可以).用 \(a[k][i]\) 表示使用 \(k\) 种颜色,至少有 ...
随机推荐
-
json对象数组按对象属性排序
var array = [ {name: 'a', phone: 1, value: 'val_4'}, {name: 'b', phone: 5, value: 'val_3'}, {name: ' ...
-
Log4Net之初步了解
原创文章,转载必需注明出处:http://www.ncloud.hk/%E6%8A%80%E6%9C%AF%E5%88%86%E4%BA%AB/log4net%E4%B9%8B%E5%88%9D%E6 ...
-
类的本质、description方法、SEL、NSLog输出增强
一.类的本质 1.类也是个对象 其实类也是一个对象,是Class类型的对象,简称“类对象” Class类型的定义 typedef struct objc_class *Class; 类名就代表着类对象 ...
-
ECSHOP 订单状态 记录
记录订单状态 order_status /* 订单状态 */ define(‘OS_UNCONFIRMED’, 0); // 未确认 define(‘OS_CONFIRMED’, ...
-
菜鸟的Xamarin.Forms前行之路——按钮的按下抬起事件的监控(可扩展至其他事件)
提问:监控按钮的点击事件,可以通过按钮的Click事件,或者Command绑定,那么如何监控按钮的按下与抬起,或者移动,长按,双击等事件? 解决方法:各个平台自定义渲染依赖注入. 共享项目PCL: 1 ...
-
CSS3学习笔记-1:CSS样式继承
自己在写css时总会遇上css样式继承的问题,好在一般问题不大,但一直也不明白css样式继承的规则,最近发现了一篇文章讲的不错,因此转载过来: 所谓CSS的继承是指被包在内部的标签将拥有外部标签的样式 ...
-
ES6躬行记(14)——函数
在前面的章节中,已陆陆续续介绍了ES6为改良函数而引入的几个新特性,本章将会继续讲解ES6对函数的其余改进,包括默认参数.元属性.块级函数和箭头函数等. 一.默认参数 在ES5时代,只能在函数体中定义 ...
-
Android应用程序签名详解
http://blog.csdn.net/lyq8479/article/details/6401093 本文主要讲解Android应用程序签名相关的理论知识,包括:什么是签名.为什么要给应用程序签名 ...
-
Android Studio 第一次启动配置
第一次启动AS前,为了避免重新下载新版本的SDK 操作如下: AS启动前,请先将bin目录的idea.properties文件中增加一行:disable.android.first.run=true ...
-
[js样式效果]具有停顿效果上下滚动方式
一般用于公告的滚动效果 <!DOCTYPE HTML> <html> <head> <meta charset="gb2312" /> ...