【题意】 一副不含王的扑克牌由52张牌组成，由红桃、黑桃、梅花、方块4组牌组成，每组13张不同的面值。 现在给定52张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。 牌的表示方法为XY，其中X为面值，为2、3、4、5、6、7、8、9、T、J、Q、K、A中的一个。 Y为花色，为S、H、D、C中的一个。 如2S、2H、TD等。 【输入格式】 第一行为一个整数T，表示共有T组测试数据。 之后每组数据占一行。 这一行首先包含一个整数N，表示给定的牌的张数，接下来N个由空格分隔的字符串，每个字符串长度为2，表示一张牌。 每组数据中的扑克牌各不相同。 【输出格式】 对于每组数据输出一行，形如”Case #X: Y”，X为数据组数，从1开始，Y为可能的方案数。 由于答案可能很大，请输出对2^64取模之后的值。 【数据范围】 1≤T≤20000, 1≤N≤52 【输入样例】 5 1 TC 2 TC TS 5 2C AD AC JC JH 4 AC KC QC JC 6 AC AD AS JC JD KD 【输出样例】 Case #1: 1 Case #2: 0 Case #3: 48 Case #4: 24 Case #5: 120

前言

由于作者做题时一头雾水，可又找不到好的题解，于是一气之下 硬干。 熬了半个多钟——终于看懂了题解——实在是妙不可言的一道计数DP。 希望自己写的东西能帮助到有需要的朋友。

思路

没有思路—— 思路大部分溶在代码里面了。 主要方法：记忆化搜索实现DP+（不算正规的）容斥原理

---

代码的主要难点主要是4行，这里重点讲一下，不过先建议读者先读懂代码其他部分。

if(a) ans+=a*dp(a-1,b,c,d); if(b) ans+=b*2*(dp(a+1,b-1,c,d)-dp(a,b-1,c,d)); if(c) ans+=c*3*(dp(a,b+1,c-1,d)-2*(dp(a+1,b,c-1,d)-dp(a,b,c-1,d))); if(d) ans+=d*4*(dp(a,b,c+1,d-1)-3*(dp(a,b+1,c,d-1)-2*(dp(a+1,b,c,d-1)-dp(a,b,c,d-1)))); $dp(a-1,b,c,d)$$2\ast (dp(a+1,b-1,c,d)-dp(a,b-1,c,d))$$3\ast (dp(a,b+1,c-1,d)-2\ast (dp(a+1,b,c-1,d)-dp(a,b,c-1,d)))$$4\ast (dp(a,b,c+1,d-1)-3\ast (dp(a,b+1,c,d-1)-2\ast (dp(a+1,b,c,d-1)-dp(a,b,c,d-1))))$

上面的第$i$行是你选了一种有$i$张的牌的合法排列方案数。 为了方便理解我们定义函数$g(a,b,c,d,i)表示有出现1次的牌a张，2次的牌b张，3次的牌c张，4次的牌d张,选择了出现次数为i的$确定一种$中一张的方案数$,特殊地，

$g(a,b,c,d,1)=dp(a-1,b,c,d)$.

对于$i>1$:

$g(a,b,c,d,2)=2\ast (dp(a+1,b-1,c,d)-g(a+1,b-1,c,d,1))$$g(a,b,c,d,3)=3\ast (dp(a,b+1,c-1,d)-g(a,b+1,c-1,d,2))$$g(a,b,c,d,4)=4\ast (dp(a,b,c+1,d-1)-g(a,b,c+1,d-1,3))$

---

我觉得上面的方法更有利于理解，但写得不好之处还望海涵。

$完结撒花\sim \sim \sim \sim \sim \sim$

---

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef unsigned long long ull; const int N=15; int m,n,num[N],c[7]; ull f[N][N][N][N];//第i维上的数为j则表示有j张出现i次的牌——而f的用途是记录方案数 char s[N],ys[150]; ull dp(int a,int b,int c,int d) { ull &ans=f[a][b][c][d]; if(~ans) return ans; ans=0;//当前有出现1次的牌a张，2次的牌b张，3次的牌c张，4次的牌d张——如果此时每个数都是正数当前位置就有4种选择。 //题目的重点在于相邻的牌面值不同。 下面讲一下(容斥)处理方法： //如果你选择了一种有x张的牌的其中一张，那么你就要先让后面任选，再减去这种牌只剩x-1张的合法方案，以防止相邻。（有点拗口，需要读者斟酌一下） //具体来讲：如果你有1张A，2张2。你此时选择了一张2， 那么方案数就是 2(22A,2A2) - 1(22A) if(a) ans+=a*dp(a-1,b,c,d); // 显然的方案数：总共有a种1张的，你可以任选(乘a),选了以后剩余a-1种1张的…… if(b) ans+=b*2*(dp(a+1,b-1,c,d)-dp(a,b-1,c,d)); //选了一种有2张的中一张，需要减去这种牌只剩1张的情况。(复制上一行的后一部分，并令a变为a+1，b变为b-1) if(c) ans+=c*3*(dp(a,b+1,c-1,d)-2*(dp(a+1,b,c-1,d)-dp(a,b,c-1,d)));//类似上面。 if(d) ans+=d*4*(dp(a,b,c+1,d-1)-3*(dp(a,b+1,c,d-1)-2*(dp(a+1,b,c,d-1)-dp(a,b,c,d-1)))); return ans; } int main() { memset(f,-1,sizeof f); f[0][0][0][0]=1; ys['A']=1;for(int i=2;i<=9;i++)ys[i+'0']=i; ys['T']=10;ys['J']=11;ys['Q']=12;ys['K']=13; scanf("%d",&m); for(int T=1;T<=m;T++) { scanf("%d",&n); memset(num,0,sizeof num); memset(c ,0,sizeof c); for(int i=1;i<=n;i++) scanf("%s",s),num[ys[s[0]]]++; for(int i=1;i<=13;i++) c[num[i]]++; printf("Case #%d: %llu\n",T,dp(c[1],c[2],c[3],c[4])); } return 0; }