$f_{a,b,c,d}$表示还有$a$组$4$个同值牌,$b$组$3$个同值牌,$c$组$2$个同值牌,$d$组$1$个同值牌未放。

显然有方程关于从 $a,b,c,d$ 中选出一组,把它拆开来放入排序中。

那么关于 $d$ 对 $1$,$d$对$1$ 每一张牌都能被选,有$f_{a,b,c,d}+=d*f_{a,b,c,d-1}$

那么关于$c$对$2$,有 $2*c$ 张牌,试想一下,两个放在一起是不允许的,减去,有$f_{a,b,c,d}+=2*c*(f_{a,b,c-1,d+1}-f_{a,b,c-1,d})$,因为第一次选的时候有$2*c$张牌可供选择,第二次选只有$1$种选择,因此是$2*c*f_{a,b,c-1,d}$。

其他两个是类似的,都是容斥原理,解释一下 $b$ 对 $3$ 吧,不允许连续两张牌存在,那么连续两张牌有 $3*b*2 $ 种选择,注意 $f_{a,b-1,c,d+1}$ 是合法方案数,只是前面放了两张一样的牌,但其中有可能出现第三张也是一样的,因此要减回去。也就是

$f_{a,b,c,d}+=3*b*(f_{a,b-1,c+1,d}-2*(f_{a,b-1,c,d+1}-f_{a,b-1,c,d}))$。

$f_{a,b,c,d}$表示还有$a$组$4$个同值牌,$b$组$3$个同值牌,$c$组$2$个同值牌,$d$组$1$个同值牌未放。

显然有方程关于从$a,b,c,d$中选出一组,把它拆开来放入排序中。

那么关于$d$对$1$,$d$对$1$ 每一张牌都能被选,有$f_{a,b,c,d}+=d*f_{a,b,c,d-1}$

那么关于$c$对$2$,有$2*c$张牌,试想一下,两个放在一起是不允许的,减去,有$f_{a,b,c,d}+=2*c*(f_{a,b,c-1,d+1}-f_{a,b,c-1,d})$,因为第一次选的时候有$2*c$张牌可供选择,第二次选只有$1$种选择,因此是$2*c*f_{a,b,c-1,d}$。

其他两个是类似的,都是容斥原理,解释一下$b$对$3$吧,不允许连续两张牌存在,那么连续两张牌有$3*b*2 $种选择,注意 $f_{a,b-1,c,d+1}$ 是合法方案数,只是前面放了两张一样的牌,但其中有可能出现第三张也是一样的,因此要减回去。也就是

$f_{a,b,c,d}+=3*b*(f_{a,b-1,c+1,d}-2*(f_{a,b-1,c,d+1}-f_{a,b-1,c,d}))$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
#define ull unsigned long long
using namespace std;
const int P=305,N=3005;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ull x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int ys[120],cnt[52],s[52];
ull f[14][14][14][14];
ull calc(int a,int b,int c,int d)
{
    if(f[a][b][c][d]!=-1)return f[a][b][c][d];
    ull &x=f[a][b][c][d];x=0;
    if(d)x+=d*calc(a,b,c,d-1);
    if(c)x+=2*c*(calc(a,b,c-1,d+1)-calc(a,b,c-1,d));//一共有c组2张同值的牌,容斥一下,如果选择了一张,那么第二张就不能选同色的,减去选同色的方案(2*c*1) 
    if(b)x+=3*b*(calc(a,b-1,c+1,d)-2*(calc(a,b-1,c,d+1)-calc(a,b-1,c,d))); 
    if(a)x+=4*a*(calc(a-1,b+1,c,d)-3*(calc(a-1,b,c+1,d)-2*(calc(a-1,b,c,d+1)-calc(a-1,b,c,d))));
    return x;
}
int main()
{
    int T;qr(T);memset(f,-1,sizeof(f));
    for(int i=2;i<=9;i++)ys['0'+i]=i;
    ys['T']=10;ys['J']=11;ys['Q']=12;ys['K']=13;ys['A']=1;
    f[0][0][0][0]=1;
    for(int t=1;t<=T;t++)
    {
        printf("Case #%d: ",t);
        for(int i=1;i<=13;i++)cnt[i]=0;
        s[1]=s[2]=s[3]=s[4]=0;
        int n;qr(n);
        for(int i=1;i<=n;i++)
        {
            char s[5];scanf("%s",s);
            ++cnt[ys[s[0]]];
        }
        for(int i=1;i<=13;i++)++s[cnt[i]];
        qw(calc(s[4],s[3],s[2],s[1]));puts("");
    }
    return 0;
}