项目编号：bzoj-1079

项目等级：Safe

项目描述：

　　

特殊收容措施：

　　DP。普通的状压状态数5¹⁵，显然TLE+MLE，我们考虑把底数和幂换一换，压成15⁵的状态数。

　　故状态设计为：f[last][rest₁][rest₂][rest₃][rest₄][rest₅]，表示上一个颜色为last，剩余k个方块的颜色种类数为rest_k的涂色方案数。

　　然后DP或记忆化即可。复杂度o(5k⁵)。

附录：

1 #include 
      
        2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 using namespace std; 5   6 static const int AwD=1000000007; static int n; 7 int r[5],f[5][20][20][20][20][20]; 8   9 int DP(const int&las)10 {11     if(!r[0]&&!r[1]&&!r[2]&&!r[3]&&!r[4]) return 1;12     if(~f[las][r[0]][r[1]][r[2]][r[3]][r[4]])13     {14         return f[las][r[0]][r[1]][r[2]][r[3]][r[4]];15     }16     int ret=0;17     range(col,0,5) if(r[col])18     {19         --r[col]; if(col) ++r[col-1];20         if(int cnt=r[col]+(col+1!=las))21         {22             (ret+=1ll*DP(col)*cnt%AwD)%=AwD;23         }24         ++r[col]; if(col) --r[col-1];25     }26     return f[las][r[0]][r[1]][r[2]][r[3]][r[4]]=ret;27 }28  29 int main()30 {31     scanf("%d",&n),memset(f,-1,sizeof f);32     range(i,0,n) {
    int c; scanf("%d",&c),++r[c-1];}33     return printf("%d\n",DP(0)),0;34 }