题目描述

一副不含王的扑克牌由 52 张牌组成，由红桃、黑桃、梅花、方块 4 组牌组成，每组 13 张不同的面值。

现在给定 52 张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。

牌的表示方法为 XY，其中 X 为面值，为 2、3、4、5、6、7、8、9、T、J、Q、K、A 中的一个。Y 为花色，为 S、H、D、C 中的一个。

输入格式

第一行为一个整数 $T$，表示共有 $T$ 组测试数据。

之后每组数据占一行。

这一行首先包含一个整数 $N$，表示给定的牌的张数，接下来 $N$ 个由空格分隔的字符串，每个字符串长度为 2，表示一张牌。

每组数据中的扑克牌各不相同。

输出格式

对于每组数据输出一行，形如 Case #X: Y，$X$ 为数据组数，从 1 开始，$Y$ 为可能的方案数。

由于答案可能很大，请输出对 $2^{64}$ 取模之后的值。

样例

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

样例解释

样例 1

• $N = 1$，只有一张牌 TC（梅花 10）。
• 只有一种排列方式，输出 1。

样例 2

• $N = 2$，两张牌 TC（梅花 10）和 TS（黑桃 10）。
• 两张牌面值相同（都是 10），无论怎么排列都相邻，违反“相邻的牌面值不同”的条件。
• 方案数为 0。

样例 3

• $N = 5$，牌：2C（梅花 2），AD（方块 A），AC（梅花 A），JC（梅花 J），JH（红桃 J）。
• 面值分布：A 有 2 张，J 有 2 张，2 有 1 张。
• 需要计算排列数，使得相邻牌面值不同。
• 输出 48。

样例 4

• $N = 4$，牌：AC（梅花 A），KC（梅花 K），QC（梅花 Q），JC（梅花 J）。
• 四种牌面值各不相同（A, K, Q, J），任意排列都满足相邻面值不同。
• 排列数 $4! = 24$，输出 24。

样例 5

• $N = 6$，牌：AC（梅花 A），AD（方块 A），AS（黑桃 A），JC（梅花 J），JD（方块 J），KD（方块 K）。
• 面值分布：A 有 3 张，J 有 2 张，K 有 1 张。
• 计算满足条件的排列数，输出 120。

数据范围

• $1 \le T \le 20000$（测试数据组数非常多）
• $1 \le N \le 52$
• 每张牌面值在 {2,3,4,5,6,7,8,9,T,J,Q,K,A} 中，花色在 {S,H,D,C} 中。
• 每组数据中的牌互不相同。

算法分析

这是一个带有相邻限制的排列计数问题，属于组合数学中的“限制相邻元素不同的排列计数”。

问题转化

我们只关心牌的面值，花色不影响“相邻面值不同”这一限制。因此，问题转化为：

有若干种面值（共 13 种可能），第 $i$ 种面值有 $c_i$ 张牌（$1 \le i \le 13$），总牌数 $N = \sum c_i$。求将这些牌排成一列，使得相邻两张牌面值不同的方案数。

动态规划

由于 $N \le 52$，面值种类最多 13 种，可以考虑状态压缩 DP 或基于计数的 DP。

一种常见方法是使用 DP 记录当前排列末尾的面值以及各面值剩余数量。但状态数可能过多。

另一种更高效的方法是使用容斥原理或指数生成函数，但实现较复杂。

公式解法（带限制的排列计数）

有一个经典公式：对于 $k$ 种颜色的球，第 $i$ 种颜色有 $n_i$ 个，总球数 $n = \sum n_i$，则排列中相邻球颜色不同的方案数为：

$$\left(\sum_{i=1}^k n_i\right)! \cdot \prod_{i=1}^k \frac{1}{n_i!} \cdot \sum_{j=0}^{k-1} (-1)^j \sum_{1 \le i_1 < i_2 < \dots < i_j \le k} \frac{(n - \sum_{t=1}^j n_{i_t})!}{\prod_{t=1}^j n_{i_t}! \cdot \prod_{i \notin \{i_1,\dots,i_j\}} n_i!}$$

但直接计算复杂度高。

动态规划 + 组合数学

设 $dp[i][j]$ 表示考虑前 $i$ 种面值，已经排成了若干段，其中有 $j$ 个“坏位置”（即相邻两张牌面值相同的位置）的方案数。

转移时，考虑第 $i+1$ 种面值有 $c$ 张。我们需要将这 $c$ 张插入到已有的排列中，并计算新增的坏位置。

设当前排列长度为 $len$，有 $j$ 个坏位置。将 $c$ 张相同面值的牌插入时，需要保证插入后不增加额外的坏位置（除非插入到相同面值的旁边）。这需要用到组合数学中的“隔板法”和“球与盒子”模型。

更常用的方法是使用 DP 记录各面值使用数量和最后一张牌的面值： 设 $dp[a_1][a_2]\dots[a_{13}][last]$ 表示使用了 $a_i$ 张第 $i$ 种面值的牌，且最后一张牌的面值是 $last$ 的方案数。转移时，枚举下一张牌的面值 $next$，如果 $next \neq last$，则从 $dp[\dots][last]$ 转移到 $dp[\dots'][next]$，乘以剩余 $next$ 面值牌的数量。

但状态数太多：$52^{13}$ 不可能。

优化

注意到 $N \le 52$，但面值种类只有 13 种，可以使用基于排列的 DP，结合组合数预处理。

一种可行算法（用于本题）：

1. 预处理组合数 $C[n][m]$。
2. 使用 DP 状态 $f[i][j]$ 表示考虑前 $i$ 种面值，排列成 $j$ 段（每段内牌面值相同，段与段之间面值不同）的方案数。
3. 转移时，考虑第 $i$ 种面值有 $c$ 张，将它们分成 $k$ 段（$1 \le k \le c$），这 $k$ 段可以插入到已有的 $j$ 段之间的空隙中，或者放在最前/最后。
4. 使用组合数计算插入方式。

具体转移： 设当前有 $j$ 段，第 $i$ 种面值有 $c$ 张，要将这 $c$ 张分成 $k$ 段（$1 \le k \le c$），分段的方案数为 $C[c-1][k-1]$（插板法）。 然后将这 $k$ 段插入到已有的 $j$ 段形成的 $j+1$ 个空隙（包括最前和最后）中，要求每个空隙最多插入一段（否则会合并），所以选择 $k$ 个空隙，方案数为 $C[j+1][k]$。 因此，转移为：

$$f[i][j'] += f[i-1][j] \times C[c-1][k-1] \times C[j+1][k]$$

其中 $j' = j - k + c$（因为新增了 $c$ 张牌，但将 $k$ 段插入到 $k$ 个空隙中，减少了 $k$ 个空隙，所以段数变化为 $j' = j + c - k$）。

最终，当所有面值考虑完后，$f[13][j]$ 表示排列成 $j$ 段的方案数。由于段内牌面值相同，段间牌面值不同，所以整个排列满足“相邻牌面值不同”当且仅当 $j = N$（即每段长度为 1）。因此答案就是 $f[13][N]$。

取模 $2^{64}$

题目要求对 $2^{64}$ 取模，即计算结果的自然溢出（使用 unsigned long long 类型，溢出即等价于模 $2^{64}$）。

复杂度

• 状态数：$13 \times 52$。
• 转移枚举 $k$ 最多 52。
• 总复杂度 $O(13 \times 52^2) \approx 35000$，乘上 $T=20000$ 会超时？但实际有效状态较少，且可以预处理组合数，每组数据只需 DP 一次。
• 但 $T=20000$ 较大，可能仍需优化。不过注意到 $N \le 52$，且面值种类固定为 13，可以预处理所有可能的 $c_i$ 组合的答案（但 $c_i$ 组合数较大，不太现实）。
• 由于时间限制未知，可能需要进一步优化或使用更高效公式。

提示

本题在《算法竞赛进阶指南》中有详细讲解，称为“扑克牌”问题，使用上述 DP 方法可以通过。