容斥原理，我们枚举选i行，选j列，选k中颜色，我们强行让i行以外，j列以外的所有点不能被涂色，那么，只有i*j个格子可以涂色，注意，是可以涂色，也可以不涂色。所以我们的答案就是sigma(c(n,i)*c(m,j)*c(c,k)*(-1)n+m+c-i-j-k*(k+1)i*j)(0<=i<=n,0<=j<=m,0<=k<=c),这样是n3的，能过的。若要log优化，详见Gold_7博客：http://gold7.is-programmer.com/
代码：
#include<cstdio>
#include<algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
int n,m,c;
ll p[410][160010],C[410][410],ans;
int main()
{
scanf("%d%d%d",&n,&m,&c);
for (int i=0;i<=max(max(n,m),c);i++)
C[i][0]=1;
for (int i=1;i<=max(max(n,m),c);i++)
for (int j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
for (int i=1;i<=c+1;i++)
{
p[i][0]=1;
for (int j=1;j<=n*m;j++)
p[i][j]=p[i][j-1]*i%mod;
}
for (int i=0;i<=n;i++)
for (int j=0;j<=m;j++)
for (int k=0;k<=c;k++)
{
ll sum=C[n][i]*C[m][j]%mod*C[c][k]%mod*p[k+1][i*j]%mod;
if ((n+m+c-i-j-k)%2) ans=(ans-sum+mod)%mod;else ans=(ans+sum)%mod;
}
printf("%lld\n",ans);
}
评论 (0)
