正题
题目链接:https://www.luogu.com.cn/problem/P6076
题目大意
给出\(n*m\)的网格，\(c\)种颜色涂色要求
- 每个格子可以染色也可以不染
- 每一行每一列至少有一个格子被染
- 每个颜色至少用一次
\(1\leq n,m,c\leq 400\)
解题思路
一个比较简单的方法就是容斥，枚举有多少染色的和不染色的行列，和枚举使用的颜色个数
\[\sum_{i=0}^c\sum_{j=0}^n\sum_{k=0}^m\binom{c}{i}\binom nj\binom mk(i+1)^{j+k}(-1)^{c+n+m-i-j-k}
\]
这样预处理就是\(O(nmc)\)的，但是可以做到更快。
设\(f_i\)表示最多染了\(i\)种颜色的方案，那么久只需要满足第二个条件了。第二个条件可以用一个容斥搞定，考虑枚举多少行没染
\[f_k=\sum_{i=1}^n(-1)^{n-i}((k+1)^{m}-1)^i
\]
这样预处理就可以做到\(O(nc)\)
这里写的是第一种，因为比较懒
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=410,P=1e9+7;
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 i=1;i<N;i++)
for(ll j=0;j<N;j++)
C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;
for(ll i=0;i<=c;i++){
pw[0]=1;
for(ll j=1;j<=n*m;j++)
pw[j]=pw[j-1]*(i+1)%P;
for(ll j=0;j<=n;j++)
for(ll k=0;k<=m;k++){
ll f=(c-i)+(n-j)+(m-k);
if(f&1)f=-1;else f=1;
(ans+=f*C[n][j]*C[m][k]%P*C[c][i]%P*pw[j*k]%P)%=P;
}
}
printf("%lld\n",(ans+P)%P);
return 0;
}