SCP-bzoj-1079

项目编号：bzoj-1079

项目等级：Safe

项目描述：

　　戳这里

特殊收容措施：

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

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

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

附录：

#include <bits/stdc++.h>
#define range(i,c,o) for(register int i=(c);i<(o);++i)
#define dange(i,c,o) for(register int i=(c);i>(o);--i)
using namespace std;
 
static const int AwD=1000000007; static int n;
int r[5],f[5][20][20][20][20][20];
 
int DP(const int&las)
{
    if(!r[0]&&!r[1]&&!r[2]&&!r[3]&&!r[4]) return 1;
    if(~f[las][r[0]][r[1]][r[2]][r[3]][r[4]])
    {
        return f[las][r[0]][r[1]][r[2]][r[3]][r[4]];
    }
    int ret=0;
    range(col,0,5) if(r[col])
    {
        --r[col]; if(col) ++r[col-1];
        if(int cnt=r[col]+(col+1!=las))
        {
            (ret+=1ll*DP(col)*cnt%AwD)%=AwD;
        }
        ++r[col]; if(col) --r[col-1];
    }
    return f[las][r[0]][r[1]][r[2]][r[3]][r[4]]=ret;
}
 
int main()
{
    scanf("%d",&n),memset(f,-1,sizeof f);
    range(i,0,n) {int c; scanf("%d",&c),++r[c-1];}
    return printf("%d
",DP(0)),0;
}