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;
}