注意数据范围就可以得到大致思路了,因为是求方案数,所以不难发现不考虑最后涂的油漆颜色时,剩余次数相同的油漆可以算作等价类。
然后就是水题了。
#include<bits/stdc++.h> using namespace std; const int mod=1000000007; typedef long long LL; int n,num[6],f[16][16][16][16][16][6]; bool vis[16][16][16][16][16][6]; LL dp(int a,int b,int c,int d,int e,int last) { if(vis[a][b][c][d][e][last]) return f[a][b][c][d][e][last]; vis[a][b][c][d][e][last]=true; if(!(a+b+c+d+e)) return f[a][b][c][d][e][last]=1; LL ans=0; if(a) ans=(ans+(a-(last==2))*dp(a-1,b,c,d,e,1))%mod; if(b) ans=(ans+(b-(last==3))*dp(a+1,b-1,c,d,e,2))%mod; if(c) ans=(ans+(c-(last==4))*dp(a,b+1,c-1,d,e,3))%mod; if(d) ans=(ans+(d-(last==5))*dp(a,b,c+1,d-1,e,4))%mod; if(e) ans=(ans+e*dp(a,b,c,d+1,e-1,5))%mod; return f[a][b][c][d][e][last]=ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int c; scanf("%d",&c); num[c]++; } printf("%lld\n",dp(num[1],num[2],num[3],num[4],num[5],0)); return 0; } /* 3 1 2 3 15 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 */