$有a_{1}个1,a_{2}个2,...,a_{n}个n(n<=15,a_{n}<=5),求排成一列相邻位不相同的方案数。$
关于这题的教训记录：
- 学会对于复杂的影响分开计，善于发现整体变化，用整体法（没错就是和物理那种差不多）。
- 推dp方程时怕边界问题不好处理时可以采用向前推的方法，就如$f[x]=f[i]+...$，可以（部分）避免越界。
我好菜啊。。除了个dp状态设计对了其他什么都没写上来qwq。基于每次插入时数字的数量都不固定，所以我可以设法将其固定下来。按顺序依次插入1,2,3,...,n即可。因为我是要统计相同不相邻方案，转移的时候肯定是插空啊，所以再设计一维表示有多少个相邻相同的($f[i][j]$)，这样就好做了。然而我在这里卡主了。。因为我看数据每个数字最多5个嘛，分类大力讨论一下的事情。然而讨论到3的时候我已经崩溃掉了。觉得写法有问题，但是又不知道怎么简化。
磕了几小时没出来QwQ，翻了题解%%%，发现还是思路狭窄了啊。每个数k个，因为要往空挡里面插，不算几张合在一起的话，分开的情况是很容易想的。而我有连续数字插入的时候，可以枚举其分组。分k组的时候，这些牌单独来看是会产生出新的$n-k$个连续位的。再看我插入时，把连续数字当做整体（就是看成一个数字），插入之前的连续位空挡相当于把他填起来了，否则无影响。所以枚举插到数字$i$,枚举之前有$j$空位连续数字，当下分为$k$组，插到之前$j$个空位里的有$l$个，之前方案$f[i][j]$，$j$个空位中选出来$l$个是$C_{j}^{l}$，剩下的非连续数字的空位还要再选$C_{sum[i-1]+1-j}^{k-l}$个，这些空位里去填$k$组，问题转为一排数字划为k组的不同方案，是经典隔板问题，有$C_{a[i]-1}^{k-1}$种。所以dp方程就出来啦。见code。可以感性认识这是不重不漏的。（？？！）
可能我组合计数还是太差了啊。几星期后到数学专题去好好补一发算了。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define dddbg(x,y,z) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl 9 using namespace std; 10 typedef long long ll; 11 typedef pair<int,int> pii; 12 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 13 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 14 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 15 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 16 template<typename T>inline T read(T&x){ 17 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 18 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 19 } 20 const ll P=1e9+7; 21 int f[101][101],fac[6],C[101][101]; 22 int T,n,s[101],sum[101]; 23 inline void inc(int&A,int B){A+=B;A>=P?A-=P:0;} 24 inline void preprocess(){ 25 C[0][0]=1; 26 for(register int i=1;i<=76;++i){C[i][0]=1;for(register int j=1;j<=52;++j)C[i][j]=(0ll+C[i-1][j]+C[i-1][j-1])%P;} 27 } 28 29 int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout); 30 preprocess();read(n); 31 for(register int i=1;i<=n;++i)read(s[i]); 32 f[1][s[1]-1]=1; 33 for(register int i=1;i<=n;++i)sum[i]=s[i]+sum[i-1]; 34 for(register int i=2;i<=n;++i) 35 for(register int j=0;j<=sum[i-1]-i+1;++j) 36 for(register int k=1;k<=s[i];++k) 37 for(register int l=0;l<=_min(j,k);++l) 38 inc(f[i][j+s[i]-k-l],f[i-1][j]*1ll*C[j][l]%P*C[sum[i-1]+1-j][k-l]%P*C[s[i]-1][k-1]%P); 39 printf("%d ",f[n][0]); 40 return 0; 41 }
hihocoder扑克牌：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define dddbg(x,y,z) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl 9 using namespace std; 10 typedef unsigned long long ull; 11 typedef pair<int,int> pii; 12 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 13 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 14 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 15 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 16 template<typename T>inline T read(T&x){ 17 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 18 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 19 } 20 const int N=14; 21 ull f[N][53],fac[5],C[54][54]; 22 int T,n,cnt[N],s[N],sum[N]; 23 char ch[4]; 24 25 int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout); 26 read(T);fac[1]=1,fac[2]=2,fac[3]=6,fac[4]=24;C[0][0]=1; 27 for(register int i=1;i<=52;++i){ 28 C[i][0]=1; 29 for(register int j=1;j<=52;++j)C[i][j]=C[i-1][j]+C[i-1][j-1]; 30 } 31 for(register int o=1;o<=T;++o){ 32 read(n);memset(cnt,0,sizeof cnt); 33 for(register int i=1;i<=n;++i){ 34 scanf("%s",ch+1);int x=ch[1]&15; 35 if(ch[1]=='A')x=1;else if(ch[1]=='T')x=10;else if(ch[1]=='J')x=11;else if(ch[1]=='Q')x=12;else if(ch[1]=='K')x=13; 36 ++cnt[x]; 37 }n=0; 38 for(register int i=1;i<=13;++i)if(cnt[i])s[++n]=cnt[i],sum[n]=s[n]+sum[n-1]; 39 memset(f,0,sizeof f);f[1][s[1]-1]=1; 40 for(register int i=2;i<=n;++i) 41 for(register int j=0;j<=sum[i-1]-i+1;++j) 42 for(register int k=1;k<=s[i];++k) 43 for(register int l=0;l<=_min(j,k);++l) 44 f[i][j+s[i]-k-l]+=f[i-1][j]*C[j][l]*C[sum[i-1]+1-j][k-l]*C[s[i]-1][k-1]; 45 for(register int i=1;i<=n;++i)f[n][0]*=fac[s[i]]; 46 printf("Case #%d: %llu ",o,f[n][0]); 47 } 48 return 0; 49 }