\(\\\)
给出\(K\)种颜料各自的个数\(C_i\)，每一个颜料只够涂一个格子，求将颜料用完，涂一排格子，每个格子只能涂一次的条件下，相邻两个格子的颜色互不相同的方案数对\(10^9+7\)取模的结果。
- \(K\in [1,15]\)，\(C_i\in [1,5]\)
\(\\\)
\(Solution\)
想的map压缩状态量记搜挂了
想的容斥记搜求组合数排列数取反挂了
正解真是神仙计数题做的还是少，基本的思路模型还是没有。
- 注意到颜色相同的颜料性质是一致的。
- 基于开始想的两种方案状态量太大，记搜也会超时，而将一类颜料看作一种之后，状态量大大减少，相当于只有\(5\)种颜料，状态里还需记录上一个颜料属于哪一类即可。
- 设计状态\(f[n_1][n_2][n_3][n_4][n_5][last]\)表示，剩余个数分别为\(1\text~5\)的颜料各有几个，上一次使用的颜料使用前剩几个，此时到用完所有颜料的总涂色方案数。
- 搜起来就很简单啦，直接考虑搜哪一位递归下去，到全是\(0\)了答案就是\(1\)，搜完累计答案时，因为一类颜料是相同的，所以直接乘上该决策的可行颜料个数。
- 一些
就我会犯的zz错误细节要注意：- 优先判断搜索的颜料还有没有再考虑搜没搜到过，否则会数组越界
- 注意到状态设计是使用前剩几个所以判断可行颜料个数时，判断时应该是上一个是否是当前\(+1\)而不是是否相同，因为你拿了一次个数一定减了一个\(1\)。
- \(+1-1\)的时候注意是成对存在的
不要光顾着-1
- 这样搜索的优越性在于，他的状态量少，代表性强，只关心相同性质的数的个数，与一些问题的精简状态量思想异曲同工
但就是想不到在这里用。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define R register#define gc getchar#define mod 1000000007llusing namespace std;typedef long long ll; inline ll rd(){ ll x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;} ll n,s[10],f[16][16][16][16][16][10]; void dfs(ll n1,ll n2,ll n3,ll n4,ll n5,ll lst){ if((n1|n2|n3|n4|n5)==0ll){f[0][0][0][0][0][lst]=1ll;return;} if(n1>0ll&&!f[n1-1][n2][n3][n4][n5][1]) dfs(n1-1,n2,n3,n4,n5,1); if(n2>0ll&&!f[n1+1][n2-1][n3][n4][n5][2]) dfs(n1+1,n2-1,n3,n4,n5,2); if(n3>0ll&&!f[n1][n2+1][n3-1][n4][n5][3]) dfs(n1,n2+1,n3-1,n4,n5,3); if(n4>0ll&&!f[n1][n2][n3+1][n4-1][n5][4]) dfs(n1,n2,n3+1,n4-1,n5,4); if(n5>0ll&&!f[n1][n2][n3][n4+1][n5-1][5]) dfs(n1,n2,n3,n4+1,n5-1,5); if(n2>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n2-(lst==3))*f[n1+1][n2-1][n3][n4][n5][2])%=mod; if(n3>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n3-(lst==4))*f[n1][n2+1][n3-1][n4][n5][3])%=mod; if(n4>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n4-(lst==5))*f[n1][n2][n3+1][n4-1][n5][4])%=mod; if(n1>0ll) (f[n1][n2][n3][n4][n5][lst]+=(n1-(lst==2))*f[n1-1][n2][n3][n4][n5][1])%=mod; if(n5>0ll)(f[n1][n2][n3][n4][n5][lst]+=n5*f[n1][n2][n3][n4+1][n5-1][5])%=mod;} int main(){ n=rd(); for(R ll i=1;i<=n;++i) ++s[rd()]; dfs(s[1],s[2],s[3],s[4],s[5],6); printf("%lld\n",f[s[1]][s[2]][s[3]][s[4]][s[5]][6]); return 0;}