【SCOI2008】着色方案

[SCOI2008]着色方案

- 题目描述
  
  有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其
  
  中第i 种颜色的油漆足够涂ci 个木块。所有油漆刚好足够涂满所有木块，即
  
  c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相
  
  邻木块颜色不同的着色方案。
  
  输入输出格式
  输入格式：
  第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。
  输出格式：
  输出一个整数，即方案总数模1,000,000,007的结果。
  
  输入输出样例
  
  输入样例#1： 复制
```
3
1 2 3
```
  输出样例#1： 复制
```
10
```
  我们设 $f[i][j]$ 表示使用了前i种油漆，有j个相邻的同色块的方案数。
- 考虑新加一种油漆i+1。我们假设有x个，我们先将他们分组。设分成了q组，那么很显然有 $C_{x-1}^{q-1}$ 种方案，并且会新产生x-q个相邻的颜色块。我们还要将分好的组插入原来的木块中间（包括两边），显然有 $sum[i]+1$ 个位置,其中有j个位置左右的颜色相同。我们在枚举这q组中的k个（这一步有有 $C_{q}^{k}$ 种方案）插入左右颜色相同的位置（这一步有 $C_{j}^{k}$ 中方案），其它的插入左右亚瑟不同的位置。插入过后颜色相同的数量变成了 $j+x-q-k$ 。将前面的所有组合数乘起来，转移方程就是 $f[i+1][j+x-q-k]+=f[i][j]*C_{x-1}^{q-1}*C_{j}^{k}*C_{q}^{k}$ 。
- 开始想到的是同种
  
  颜色的油漆一个一个地加入，但是在加入的时候还要考虑相同颜色与不同颜色的块要分开考虑，最后还要去重。。。就是各种复杂的操作，最后还是没调出来。
- 所以有些题适合逐个DP，有些适合一组一组地DP。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#define ll long long
#define N 20
#define mod 1000000007

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n;
int sum[N],num[N];
ll c[80][80],f[N][80];
int main() {
	c[0][0]=1;
	for(int i=1;i<=75;i++)
		for(int j=0;j<=i;j++)
			c[i][j]=(!j||j==i)?1:(c[i-1][j-1]+c[i-1][j])%mod;
	n=Get();
	for(int i=1;i<=n;i++) {
		num[i]=Get();
		sum[i]=num[i]+sum[i-1];
	}
	f[1][num[1]-1]=1;
	for(int i=1;i<n;i++) {
		for(int j=0;j<=75;j++) {
			if(!f[i][j]) continue ;
			for(int q=1;q<=num[i+1];q++) {//分成q组 
				if(q>sum[i]+1) continue ;
				for(int k=0;k<=q;k++) {//其中k组放在相同块中 
					if(k>j||q-k>sum[i]+1-j||j+num[i+1]-q-k<0) continue ;
					(f[i+1][j+num[i+1]-q-k]+=f[i][j]*c[num[i+1]-1][q-1]%mod*c[j][k]%mod*c[sum[i]+1-j][q-k])%=mod;
				}
			}
		}
	}
	cout<<f[n][0];
	return 0;
}

【SCOI2008】着色方案

[SCOI2008]着色方案

题目描述

输入输出格式

输入输出样例