软件网站设计师培训,优化公司网站排名,京东的网站建设介绍,商贸网站建设正题
题目链接:https://www.luogu.com.cn/problem/P6076 题目大意
给出n∗mn*mn∗m的网格#xff0c;ccc种颜色涂色要求
每个格子可以染色也可以不染每一行每一列至少有一个格子被染每个颜色至少用一次 1≤n,m,c≤4001\leq n,m,c\leq 4001≤n,m,c≤400 解题思路
一个比较简…正题
题目链接:https://www.luogu.com.cn/problem/P6076 题目大意
给出n∗mn*mn∗m的网格ccc种颜色涂色要求
每个格子可以染色也可以不染每一行每一列至少有一个格子被染每个颜色至少用一次
1≤n,m,c≤4001\leq n,m,c\leq 4001≤n,m,c≤400 解题思路
一个比较简单的方法就是容斥枚举有多少染色的和不染色的行列和枚举使用的颜色个数 ∑i0c∑j0n∑k0m(ci)(nj)(mk)(i1)jk(−1)cnm−i−j−k\sum_{i0}^c\sum_{j0}^n\sum_{k0}^m\binom{c}{i}\binom nj\binom mk(i1)^{jk}(-1)^{cnm-i-j-k}i0∑cj0∑nk0∑m(ic)(jn)(km)(i1)jk(−1)cnm−i−j−k
这样预处理就是O(nmc)O(nmc)O(nmc)的但是可以做到更快。
设fif_ifi表示最多染了iii种颜色的方案那么久只需要满足第二个条件了。第二个条件可以用一个容斥搞定考虑枚举多少行没染 fk∑i1n(−1)n−i((k1)m−1)if_k\sum_{i1}^n(-1)^{n-i}((k1)^{m}-1)^ifki1∑n(−1)n−i((k1)m−1)i 这样预处理就可以做到O(nc)O(nc)O(nc)
这里写的是第一种因为比较懒 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N410,P1e97;
ll n,m,c,C[N][N],pw[N*N],ans;
signed main()
{scanf(%lld%lld%lld,n,m,c);C[0][0]1;for(ll i1;iN;i)for(ll j0;jN;j)C[i][j](C[i-1][j](j?C[i-1][j-1]:0))%P; for(ll i0;ic;i){pw[0]1;for(ll j1;jn*m;j)pw[j]pw[j-1]*(i1)%P;for(ll j0;jn;j)for(ll k0;km;k){ll f(c-i)(n-j)(m-k);if(f1)f-1;else f1;(ansf*C[n][j]*C[m][k]%P*C[c][i]%P*pw[j*k]%P)%P;}}printf(%lld\n,(ansP)%P);return 0;
}
