扑克牌

形式化题目

给定 52 张扑克中的若干张（同面值至多 4 张、不同花色），求把它们排成一列且相邻两张面值不同的方案数，答案对 $2^{64}$ 取模。

正解

思路

1. 花色无关，只看面值分布

同面值的牌花色不同但彼此等价（约束只看面值），状态只需记录「每个面值还剩几张」。按剩余张数分 4 档（1/2/3/4 张），每档记「有多少个面值」，4 档 × 4 bit = 16 bit；外加「上一张牌的面值档次」2 bit，状态总数极小。

2. 记忆化搜索

$f(\text{code})$ ：状态 code 下放完剩余牌的方案数。枚举下一档 size：

该档有 pick = left - (last==size) 个面值可选（上一张同面值的面值被排除）；
「从 size 个同面值的不同牌里选哪张」×「插到 pick 个可选面值的哪个位置」相互独立，贡献因子 $size \cdot pick$ ；
转移后该面值掉档，递归。

@cache 记忆化；答案对 $2^{64}$ 取模，Python 整数不溢出，用 & ((1<<64)-1) 主动掩码。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 洗牌：状态只记「还剩 k 张的面值各有多少个」+ 上一张牌的面值档次
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int SHIFT[4] = {0, 4, 8, 12}; // 高位中“恰好还剩 k 张的面值个数”占的位偏移，k = size-1
const int CODE_MAX = 1 << 18;       // code = body<<2 | (上一张档次)，body 只有 16 位

int cnt[128];                   // 每个面值出现了几次（牌数 <= 20000，面值最多 52 种）
ull memo[CODE_MAX];
char done[CODE_MAX];

// 状态码 code：牌集合按相邻面值不同排成一列有多少种放法（答案对 2^64 取模）
ull free_ways(int code) {
    if (done[code]) {
        return memo[code];
    }
    done[code] = 1;
    int body = code >> 2, last = code & 3;
    if (!body) {
        memo[code] = 1; // 牌放完了，空后缀算一种放法
        return 1;
    }
    ull total = 0;
    for (int size = 1; size <= 4; size++) {
        int left = (body >> SHIFT[size - 1]) & 15; // 还剩 size 张的面值有多少个
        int pick = left - (last == size);          // 上一张同面值的牌后面这个空位不能放
        if (pick <= 0) {
            continue;
        }
        int nxt = body - (1 << SHIFT[size - 1]); // 该面值掉到 size-1 档
        if (size > 1) {
            nxt += 1 << SHIFT[size - 2];
        }
        total += (ull)size * pick * free_ways(nxt << 2 | (size - 1));
    }
    memo[code] = total;
    return total;
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) {
        return 0;
    }
    for (int tc = 1; tc <= T; tc++) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < 128; i++) {
            cnt[i] = 0;
        }
        char card[16];
        for (int i = 0; i < n; i++) {
            scanf("%15s", card);
            cnt[(unsigned char)card[0]]++;
        }
        // 只需统计「剩 k 张的面值有几个」
        int by_size[5] = {0, 0, 0, 0, 0};
        for (int i = 0; i < 128; i++) {
            if (cnt[i]) {
                by_size[cnt[i]]++;
            }
        }
        int code = 0;
        for (int size = 1; size <= 4; size++) {
            code += by_size[size] << SHIFT[size - 1];
        }
        code <<= 2;
        printf("Case #%d: %llu\n", tc, free_ways(code));
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 23:48
# update_at: 2026-10-01 23:48

import sys
from collections import Counter
from functools import cache

MASK = (1 << 64) - 1  # 答案对 2^64 取模；Python 整数不溢出，只能主动掩码
SHIFT = (0, 4, 8, 12)  # 状态码高位中“恰好还剩 k 张的面值个数”占的位偏移，k = size-1


@cache
def free_ways(code: int) -> int:
    """状态码 code 对应的牌集合，按相邻面值不同排成一列有多少种放法。

    花色不参与冲突，只有“面值”约束相邻关系，所以一个面值只需记住还剩几张
    （0~4 张，而 0 张的面值用不着记录）。高位按剩余张数分 4 档存面值个数，
    低 2 位存上一张牌的面值档次（size-1），0 表示还没放过任何牌——它不是任何
    真实档次，所以天然不会和“上一张同面值”的判断冲突。
    """
    body, last = code >> 2, code & 3
    if not body:
        return 1  # 牌放完了，空后缀算一种放法

    total = 0
    for size, shift in enumerate(SHIFT, 1):
        left = body >> shift & 15           # 还剩 size 张的面值有多少个
        pick = left - (last == size)        # 上一张同面值的牌后面这个空位不能放
        if pick <= 0:
            continue
        nxt = body - (1 << shift)           # 该面值掉到 size-1 档
        if size > 1:
            nxt += 1 << SHIFT[size - 2]
        # size 种“选哪张牌”与 pick 个“插进哪个空位”相互独立，直接相乘
        total += size * pick * free_ways(nxt << 2 | size - 1)
    return total & MASK


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    T = int(next(data))

    for case in range(1, T + 1):
        n = int(next(data))
        cards = [next(data) for _ in range(n)]  # 每张牌形如 2S，面值取第 0 个字符

        # 只需统计“剩 k 张的面值有几个”，花色与面值具体是什么都不影响答案。
        by_size = Counter(Counter(card[:1] for card in cards).values())
        code = sum(cnt << SHIFT[size - 1] for size, cnt in by_size.items()) << 2
        out.append(f"Case #{case}: {free_ways(code)}")

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：状态数 = 面值分布档位划分数（很少），单状态转移 $O(4)$ ，总代价极小。
空间复杂度： $O(\text{状态数})$ （记忆化缓存）。

总结

「同值多张 + 相邻不同」的排列计数：按剩余张数分档压缩状态，档位个数而非张数决定状态规模。
花色等价类合并是把 $2^{52}$ 级问题压到可解的关键。
模 $2^{64}$ 直接掩码即可，无需取模运算。

目录

形式化题目

正解

思路

1. 花色无关，只看面值分布

2. 记忆化搜索

代码

复杂度

总结