BZOJ 1079 着色

Link

Solution 1

脑洞超大 首先考虑最最暴力的做法,把每种颜色的剩余个数压起来的状压DP肯定是可以做的, \(f[i][S]\)表示序列中的颜色的个数的状态为\(S\),第一个位置颜色是\(i\)的方案数目,转移就枚举就好了 只是状态有\(15\times 5^{15}\)个(233)。(PS:排队题?) 然后考虑做了什么无用功:个数相同的颜色是本质相同的,一种方案的颜色置换一下就是另一个方案。因此,要开一个相当大的脑洞: \(f[i][S]\)分别记录剩余\(1\sim 5\)个可用块的颜色数,\(i\)表示上一位放的颜色的剩余的个数。 DFS,枚举当前要放的色块的可用个数,然后相应加减,进入下一层DFS,累计返回的答案。 具体做法是, 现在要放的一种剩下\(c\)个可用块的颜色,那么计算\(res=S[c]--,S[c-1]++,{\rm DFS}(c,S)\)。 假如说\(i\not=c+1\),那么答案累加\(res*S[c]\),否则累加\(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]\)表示构造了含有所有前\(i\)种颜色的色块的序列,有\(j\)同色相邻 那么答案就是\(f[K][0]\) 考虑转移 现在有\(cnt[i+1]\)个第\(i+1\)种颜色的色块,要把它们分到已经有的长度为\(pref[i] (pref[i]=\sum\limits_{j=1}^i cnt[i])\)的序列中。 大体可以用这些色块搞这三件事: 1. 确立社会主义市场经济

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

然后这个过程看起来是很复杂的,其实经过一番抽象可以看成这样的东西: 把\(cnt[i+1]\)个色块,分成\(dc\)个组,把这些组的前\(div\)个塞到已有的相邻同色对中间,后\(dc-div\)个塞到相邻的不同色对中间。 那么这样的话,新的序列就会多出\((cnt[i+1]-dc)-div\)对相邻同色对 那么这样构造的方案数目呢? 把\(cnt[i+1]\)个分\(dc\)组,插板法,\(C_{cnt[i+1]-1}^{dc-1}\) 塞前\(div\)组,有\(C_j^{div}\)种方法 剩下的,有\(C_{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;
}

不得不说,

一道题的两种做法都这么巧妙优美凝练,这真**是个好题!

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利