当前位置: 首页 > news >正文

P6076 [JSOI2015] 染色问题 分析

题目概述

\(n\times m\) 的棋盘,现在需要涂 \(k\) 种颜色上去,需要满足:

  • 每一行至少有一个格子被涂色。
  • 每一列至少有一个格子被涂色。
  • \(k\) 种颜色必须都在这个棋盘上出现。

数据范围:\(1\leq n,m,k\leq 400\)

分析

经典题目,记录一下。

多重容斥的经典题目。

我们考虑枚举 \(i,j,t\) 表示至少有 \(i\) 行格子被涂色,至少有 \(k\) 行格子被涂色,至少有 \(k\) 种颜色涂了。

所以说:

\[ans=\sum_{i=0}^n\sum_{j=0}^m\sum_{t=0}^k(-1)^{i+j+k}C_{n}^iC_{m}^jC_{k}^t F(i,j,t) \]

其中 \(F(i,j,t)\) 表示这种情况下的方案数是多少。

那么对于剩下的行数、列数的格子有 \((n-i)\times (m-j)\) 个。

每个格子有两种选择:

  • 不被涂色。
  • 涂成剩下 \((k-t)\) 种颜色下的一种。

也就是说,每个格子有 \((k-t+1)\) 种选择,所以:

\[F(i,j,t)=(k-t+1)^{(n-i)\times (m-j)} \]

那么就直接这样做就行了。

代码

时间复杂度 \(\mathcal{O}(nmc)\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 405
using namespace std;
const int mod = 1e9 + 7;
int qpow(int a,int b) {int res = 1;while(b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
int jc[N],inv[N];
int C(int a,int b) {if (a < 0 || b < 0 || a < b) return 0;return jc[a] * inv[b] % mod * inv[a - b] % mod;
}
signed main(){jc[0] = jc[1] = inv[0] = inv[1] = 1;for (int i = 2;i < N;i ++) jc[i] = jc[i - 1] * i % mod,inv[i] = (mod - mod / i) * inv[mod % i] % mod;for (int i = 2;i < N;i ++) inv[i] = inv[i - 1] * inv[i] % mod;int ans = 0,n,m,k;cin >> n >> m >> k;for (int i = 0;i <= n;i ++)for (int j = 0;j <= m;j ++)for (int t = 0;t <= k;t ++) {int xs = ((i + j + t & 1) ? -1 : 1);ans = (ans + (xs * C(n,i) * C(m,j) % mod * C(k,t) % mod * qpow((k - t + 1),(n - i) * (m - j)) % mod + mod) % mod) % mod;}cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=34785

相关文章:

  • CF2154 Codeforces Round 1060 (Div. 2) 游记
  • 2025 最新推荐!国际物流 / 东南亚 / 跨境电商清关公司排行榜:精选优质机构助企业高效通关
  • 2025 年济南画室最新推荐品牌口碑排行榜权威发布,涵盖小班教学与全封闭管理机构,助力艺考生选优质画室
  • 2025 年最新货代公司排行榜:国内优质企业权威推荐,助力企业精准挑选靠谱合作伙伴泰国/印尼/马来/日本/东南亚货代公司推荐
  • C#转java的最好利器easy-query就是efcore4j sqlsugar4j freesql4j
  • 加密货币投资风控方案
  • 物联网设备漏洞及其对国家安全的影响分析
  • CF2128D Sum of LDS
  • 2025.10.20——1黄
  • 完整教程:华硕NUC 15Pro 系列 舒适办公新体验的理想之选
  • Cisco IOS XRv 9000 Router 25.1.2 MD - 服务提供商边缘虚拟路由器
  • Roslyn 技术解析:如何利用它做代码生成?
  • Cisco IOS XRv 9000 Router 24.4.2 MD - 服务提供商边缘虚拟路由器
  • 深度学习注意力机制新篇章
  • CSP-S模拟35
  • 解密prompt系列62. Agent Memory一览 - MATTS CFGM MIRIX
  • MIT推出SEAL框架:实现AI自我迭代新突破
  • 首款“全国产”高性能GPU发布
  • 2025.10.20+7[未完]
  • 读人形机器人32读后总结与感想兼导读
  • 语音助手减少不必要澄清问题的技术突破
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名知识管理工具生态需求洞察
  • CH32V003
  • 232
  • 231233
  • 231
  • ww
  • 高级语言:面向过程和面向对象
  • Codeforces Round 1060 (Div. 2)
  • Luogu P14260 期待(counting) 题解 [ 蓝 ] [ 前缀和 ] [ 组合计数 ]