BZOJ4487 [Jsoi2015]染色问题

时间:2022-09-23 16:29:59

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]染色问题的更多相关文章

  1. &lbrack;bzoj4487&rsqb;&lbrack;Jsoi2015&rsqb;染色&lowbar;容斥原理

    染色 bzoj-4487 Jsoi-2015 题目大意:给你一个n*m的方格图,在格子上染色.有c中颜色可以选择,也可以选择不染.求满足条件的方案数,使得:每一行每一列都至少有一个格子被染色,且所有的 ...

  2. bzoj4487&lbrack;Jsoi2015&rsqb;染色问题 容斥&plus;组合

    4487: [Jsoi2015]染色问题 Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 211  Solved: 127[Submit][Status ...

  3. 2019&period;02&period;09 bzoj4487&colon; &lbrack;Jsoi2015&rsqb;染色问题(容斥原理)

    传送门 题意简述: 用ccc中颜色给一个n∗mn*mn∗m的方格染色,每个格子可涂可不涂,问最后每行每列都涂过色且ccc中颜色都出现过的方案数. 思路: 令fi,j,kf_{i,j,k}fi,j,k​ ...

  4. &lbrack;BZOJ4487&rsqb;&lbrack;JSOI2015&rsqb;染色问题&lpar;容斥&rpar;

    一开始写了7个DP方程,然后意识到这种DP应该都会有一个通式. 三个条件:有色行数为n,有色列数为m,颜色数p,三维容斥原理仍然成立. 于是就是求:$\sum_{i=0}^{n}\sum_{j=0}^ ...

  5. BZOJ4487 JSOI2015染色问题(组合数学&plus;容斥原理)

    逐个去除限制.第四个限制显然可以容斥,即染恰好c种颜色的方案数=染至多c种颜色的方案数-染至多c-1种颜色的方案数+染至多c-2种颜色的方案数…… 然后是限制二.同样可以容斥,即恰好选n行的方案数=至 ...

  6. 【BZOJ4487】&lbrack;JSOI2015&rsqb;染色问题(容斥)

    [BZOJ4487][JSOI2015]染色问题(容斥) 题面 BZOJ 题解 看起来是一个比较显然的题目? 首先枚举一下至少有多少种颜色没有被用到过,然后考虑用至多\(k\)种颜色染色的方案数. 那 ...

  7. 【bzoj4487】&lbrack;Jsoi2015&rsqb;染色问题 容斥原理

    题目描述 棋盘是一个n×m的矩形,分成n行m列共n*m个小方格.现在萌萌和南南有C种不同颜色的颜料,他们希望把棋盘用这些颜料染色,并满足以下规定: 1.  棋盘的每一个小方格既可以染色(染成C种颜色中 ...

  8. 【BZOJ4487】&lbrack;JSOI2015&rsqb; 染色问题(高维容斥)

    点此看题面 大致题意: 有一个\(n*m\)的矩形,先让你用\(C\)种颜色给它染色.每个格子可染色可不染色,但要求每行每列至少有一个小方格被染色,且每种颜色至少出现一次.求方案数. 高维容斥 显然题 ...

  9. 【题解】JSOI2015染色问题

    好像这个容斥还是明显的.一共有三个要求,可以用组合数先满足一个,再用容斥解决剩下的两个维.(反正这题数据范围这么小,随便乱搞都可以).用 \(a[k][i]\) 表示使用 \(k\) 种颜色,至少有 ...

随机推荐

  1. json对象数组按对象属性排序

    var array = [ {name: 'a', phone: 1, value: 'val_4'}, {name: 'b', phone: 5, value: 'val_3'}, {name: ' ...

  2. 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 ...

  3. 类的本质、description方法、SEL、NSLog输出增强

    一.类的本质 1.类也是个对象 其实类也是一个对象,是Class类型的对象,简称“类对象” Class类型的定义 typedef struct objc_class *Class; 类名就代表着类对象 ...

  4. ECSHOP 订单状态 记录

    记录订单状态 order_status /* 订单状态 */ define(‘OS_UNCONFIRMED’,            0); // 未确认 define(‘OS_CONFIRMED’, ...

  5. 菜鸟的Xamarin&period;Forms前行之路——按钮的按下抬起事件的监控&lpar;可扩展至其他事件&rpar;

    提问:监控按钮的点击事件,可以通过按钮的Click事件,或者Command绑定,那么如何监控按钮的按下与抬起,或者移动,长按,双击等事件? 解决方法:各个平台自定义渲染依赖注入. 共享项目PCL: 1 ...

  6. CSS3学习笔记-1:CSS样式继承

    自己在写css时总会遇上css样式继承的问题,好在一般问题不大,但一直也不明白css样式继承的规则,最近发现了一篇文章讲的不错,因此转载过来: 所谓CSS的继承是指被包在内部的标签将拥有外部标签的样式 ...

  7. ES6躬行记(14)——函数

    在前面的章节中,已陆陆续续介绍了ES6为改良函数而引入的几个新特性,本章将会继续讲解ES6对函数的其余改进,包括默认参数.元属性.块级函数和箭头函数等. 一.默认参数 在ES5时代,只能在函数体中定义 ...

  8. Android应用程序签名详解

    http://blog.csdn.net/lyq8479/article/details/6401093 本文主要讲解Android应用程序签名相关的理论知识,包括:什么是签名.为什么要给应用程序签名 ...

  9. Android Studio 第一次启动配置

    第一次启动AS前,为了避免重新下载新版本的SDK 操作如下: AS启动前,请先将bin目录的idea.properties文件中增加一行:disable.android.first.run=true ...

  10. &lbrack;js样式效果&rsqb;具有停顿效果上下滚动方式

    一般用于公告的滚动效果 <!DOCTYPE HTML> <html> <head> <meta charset="gb2312" /&gt ...