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;

}

巴特西

BZOJ4487 [Jsoi2015]染色问题

BZOJ4487 [Jsoi2015]染色问题

题目描述

题目分析

是代码呢

最新文章

热门文章