BZOJ 1079 着色

发表于 | 更新于

Link

Solution 1

脑洞超大 首先考虑最最暴力的做法，把每种颜色的剩余个数压起来的状压DP肯定是可以做的， f[i][S]f[i][S]表示序列中的颜色的个数的状态为SS，第一个位置颜色是ii的方案数目，转移就枚举就好了 只是状态有15×51515\times 5^{15}个(233)。（PS：排队题？） 然后考虑做了什么无用功：个数相同的颜色是本质相同的，一种方案的颜色置换一下就是另一个方案。因此，要开一个相当大的脑洞： f[i][S]f[i][S]分别记录剩余1∼51\sim 5个可用块的颜色数，ii表示上一位放的颜色的剩余的个数。 DFS，枚举当前要放的色块的可用个数，然后相应加减，进入下一层DFS，累计返回的答案。 具体做法是， 现在要放的一种剩下cc个可用块的颜色，那么计算 。 假如说 ，那么答案累加res∗S[c]res*S[c]，否则累加res∗(S[c]−1)res*(S[c]-1)。 仔细想想是非常妙的，把本质相同的状态一起计算，通过乘法原理累计答案。

Code 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "lucida"
const int P=1000000007;
struct Five {
	int a[6];
	Five(int n[]) {
		for(int i=0;i<=5;++i)
			a[i]=n[i];
	}
	int &operator [](int x) {
		return a[x];
	}
};
int64 f[6][16*16*16*16*16];
int Hash(Five s) {
	int res=0;
	for(int i=1;i<=5;++i)
		(res*=16)+=s[i];
	return res;
}
int64 DP(int last,Five s) {
	int code=Hash(s);
	if(~f[last][code]) return f[last][code];
	int64 res=0;
	for(int i=1;i<=5;++i) if(s[i]) {
		--s[i],++s[i-1];
		(res+=((s[i]+1)-(last==i+1))*DP(i,s))%=P;
		++s[i],--s[i-1];
	}
	return f[last][code]=res;
}
int main() {
	freopen("input","r",stdin);
	int num[6];memset(num,0,sizeof(num));
	int k;is>>k;
	for(int i=1;i<=k;++i) {
		int c;is>>c;
		num[c]++;
	}
	memset(f,-1,sizeof(f));
	for(int i=0;i<=5;++i) f[i][0]=1;
	int64 Ans=DP(0,Five(num));
	os<<Ans<<'\n';
	return 0;
}

Solution 2

发现有大神给出了更科学的清真做法，其实和那个排队神似 f[i][j]f[i][j]表示构造了含有所有前ii种颜色的色块的序列，有jj对同色相邻 那么答案就是f[K][0]f[K][0] 考虑转移 现在有cnt[i+1]cnt[i+1]个第i+1i+1种颜色的色块，要把它们分到已经有的长度为pref[i](pref[i]=∑j=1icnt[i])pref[i] (pref[i]=\sum\limits_{j=1}^i cnt[i])的序列中。 大体可以用这些色块搞这三件事： 1. 确立社会主义市场经济

  1. 放到一起，组成新的相邻同色对
  2. 塞到已经有的相邻同色对中，无情地拆散
  3. 老老实实地分到一些相邻不同色的对的中间

然后这个过程看起来是很复杂的，其实经过一番抽象可以看成这样的东西： 把cnt[i+1]cnt[i+1]个色块，分成dcdc个组，把这些组的前divdiv个塞到已有的相邻同色对中间，后dc−divdc-div个塞到相邻的不同色对中间。 那么这样的话，新的序列就会多出(cnt[i+1]−dc)−div(cnt[i+1]-dc)-div对相邻同色对 那么这样构造的方案数目呢？ 把cnt[i+1]cnt[i+1]个分dcdc组，插板法，Ccnt[i+1]−1dc−1C_{cnt[i+1]-1}^{dc-1} 塞前divdiv组，有CjdivC_j^{div}种方法 剩下的，有Cpref[i]+1−jdc−divC_{pref[i]+1-j}^{dc-div}种方法

Code 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "lucida"
const int MAXN=80,P=1e9+7;
int64 f[MAXN][MAXN],C[MAXN][MAXN];
int cnt[MAXN],pref[MAXN];
struct PREP{PREP() {
	C[0][0]=1;
	for(int i=1;i<MAXN;++i) {
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	}
}}srO_Orz;
int main() {
	freopen("input","r",stdin);
	int K;is>>K;
	for(int i=1;i<=K;++i) {
		is>>cnt[i];
		pref[i]=pref[i-1]+cnt[i];
	}
	f[0][0]=1;
	for(int i=0;i<K;++i)
		for(int j=0;j<=pref[i];++j)
			for(int dc=1;dc<=cnt[i+1];++dc)
				for(int div=0,g;div<=dc;++div)
					if((g=j+(cnt[i+1]-dc)-div)>=0)
						(f[i+1][g]+=f[i][j]*C[cnt[i+1]-1][dc-1]%P*C[j][div]%P*C[pref[i]+1-j][dc-div])%=P;
					else 
						break;
	int64 Ans=f[K][0];
	os<<Ans<<'\n';
	return 0;
}

不得不说，

一道题的两种做法都这么巧妙优美凝练，这真＊＊是个好题！