(HihoCoder1159)
说实话，这道题很有意思，像这种不断转换的题目是很有趣的。
(13)种面值，肯定有人一打开时就想来一个(13)维数组，可惜不行，好吧真的不行……
(First)转换：我们可以认为有(13)种物品，每种至多有(4)个（其实这相当于模型抽象，不过为了不炒饭，就先这么说了……）
然而，状态还是不好出来，很多人都会想到(f[l1][l2][l3][l4])这样的状态。
即(l1)为剩下(1)种物品个数，(l2)为剩下(2)种物品个数，(l3)为剩下(3)种物品个数，(l4)为剩下(4)种物品个数。
然而无法转移，明显的，转移和上一个状态有关，但是如果我们将上一个面值保留下来时，当前面值也要考虑，维度肯定要大幅度修改，有问题。
(Second)转换：这是一个很神奇的地方，即记一个(las)表示上一次选择的物品的种类未放时该种类剩下的数量，将这个(las)加入状态中即可。
至于为什么可行，我们想一下就知道，我们其实并不关心到底是哪一种，仅关心相邻种类的不相等。
转移的过程如下：
例如：我们求(f[l1][l2][l3][l4][3])时（先内定(l1,l2,l3,l4)不为零吧）
可以直接转移：
(f[l1][l2][l3][l4][3]+=l1*f[l1-1][l2][l3][l4][1]×1;)
(f[l1][l2][l3][l4][3]+=l3*f[l1][l2+1][l3-1][l4][3]*3;)
(f[l1][l2][l3][l4][3]+=l4*f[l1][l2][l3+1][l4-1][4]*4;)
但对于(2)就要注意了，因为当前的(2)就是上一次的(3)，因为不能有相同的种类，所以要(-1)
(f[l1][l2][l3][l4][3]+=(l2-1)*f[l1+1][l2-1][l3][l4][3]*2;)
因此代码就出来啦：
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
int n,f[20][20][20][20][20],num[5],c[20];
inline int Dfs(int l1,int l2,int l3,int l4,int las)
{
int ans=0;
if(!(l1|l2|l3|l4)) return f[l1][l2][l3][l4][las]=1;
if(f[l1][l2][l3][l4][las]) return f[l1][l2][l3][l4][las];
if(l1) ans+=(l1-(las==2))*Dfs(l1-1,l2,l3,l4,1);
if(l2) ans+=(l2-(las==3))*Dfs(l1+1,l2-1,l3,l4,2)*2;
if(l3) ans+=(l3-(las==4))*Dfs(l1,l2+1,l3-1,l4,3)*3;
if(l4) ans+=l4*Dfs(l1,l2,l3+1,l4-1,4)*4;
return f[l1][l2][l3][l4][las]=ans;
}
main(){
#ifndef ONLINE_JUDGE
freopen("Text1.in","r",stdin);
#endif
int T=read();
for(int Itst=1;Itst<=T;Itst++)
{
n=read();
memset(c,0,sizeof(c));
memset(num,0,sizeof(num));
printf("Case #%llu: ",Itst);
for(int i=1;i<=n;i++)
{
char s[5];scanf("%s",s);
if(s[0]>='0'&&s[0]<='9') c[s[0]-'0']++;
else if(s[0]=='T') c[10]++;
else if(s[0]=='J') c[11]++;
else if(s[0]=='Q') c[12]++;
else if(s[0]=='K') c[13]++;
else if(s[0]=='A') c[1]++;
}
for(int i=1;i<=13;i++) num[c[i]]++;
printf("%llu
",Dfs(num[1],num[2],num[3],num[4],0));
}
}