Project Euler 369

发表于 分类于 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

Project Euler 369

题目

Badugi

In a standard \(52\) card deck of playing cards, a set of \(4\) cards is a Badugi if it contains \(4\) cards with no pairs and no two cards of the same suit.

Let \(f(n)\) be the number of ways to choose \(n\) cards with a \(4\) card subset that is a Badugi. For example, there are \(2598960\) ways to choose five cards from a standard \(52\) card deck, of which \(514800\) contain a \(4\) card subset that is a Badugi, so \(f(5) = 514800\).

Find \(\sum f(n)\) for \(4 \le n \le 13\).

解决方案

一副标准扑克牌可以看成一个 \(13\times 4\) 的网格：行表示点数 \(1\sim 13\)，列表示四种花色。选出一手 \(n\) 张牌，就等价于在这个网格里选出 \(n\) 个格子。一个 \(4\) 张 Badugi 子集的含义是：这 \(4\) 张牌的点数两两不同、花色也两两不同。用网格语言说，就是：存在 \(4\) 个被选中的格子，使得它们不在同一行也不在同一列，即形成一个 \(4\times 4\) 的置换矩阵形状。

因此，把问题改写成二分图：左侧顶点是四个花色；右侧顶点是 \(13\) 个点数；若某张牌（某花色、某点数）被选中，就在对应两个顶点之间连一条边。那么存在一组 Badugi 子集当且仅当这张二分图里存在一个覆盖四个花色的匹配（匹配大小为 \(4\)）。因为匹配选的四条边必然连接四个不同花色与四个不同点数，对应四张两两不同行列的牌。

因此我们要数的是：大小为 \(n\) 的边集（即选牌集合）中，二分图是否存在覆盖四个花色的匹配。

把四种花色编码为\(\Sigma=\{0,1,2,3\}.\)

对任意点数行前缀 \([1..r]\)（即只看前 \(r\) 个点数），以及从这些行中选出的若干牌集合 \(C\)，定义一个可达集合族\(\mathcal{R}(C)\subseteq 2^\Sigma\)为所有满足下述条件的花色子集 \(S\) 的集合：

\(S\in\mathcal{R}(C)\) 当且仅当存在一个大小为 \(|S|\) 的子集 \(B\subseteq C\)，使得

  1. \(B\) 中的牌点数两两不同；
  2. \(B\) 中的牌花色两两不同；
  3. \(B\) 所用花色集合恰为 \(S\)。

也就是说，\(\mathcal{R}(C)\) 记录了“在当前已选牌中，能用互异点数的方式，匹配到哪些花色集合”。

为了压缩表示，把 \(2^\Sigma\) 中的 \(16\) 个子集按 4-bit 掩码编码。定义\(\displaystyle{M(C)=\sum_{S\subseteq \Sigma}\mathbf 1[S\in\mathcal{R}(C)]\cdot 2^{\mathrm{code}(S)},}\)其中 \(\mathrm{code}(S)\in\{0,\dots,15\}\) 是集合 \(S\) 的二进制编码：若 \(i\in S\) 则第 \(i\) 位为 \(1\)。

接着引入按行推进的计数DP：令\(D_{r,c}(M)\)表示：只考虑前 \(r\) 行（前 \(r\) 个点数），一共选了 \(c\) 张牌，且其可达掩码 \(M(C)\) 等于 \(M\) 的方案数。

初始条件是\(D_{0,0}(1)=1,\)因为没选任何牌时仅空集 \(S=\varnothing\) 可达，其对应的 \(M\) 只有 \(\mathrm{code}(\varnothing)=0\) 这一位为 \(1\)，即数值为 \(1\)。

在第 \(r\) 行（某个点数）上，四种花色各有一张牌。设这一行我们选择的花色集合为\(A\subseteq \Sigma.\)这一步会把 \(|A|\) 张牌加入总选牌集合。

关键是：Badugi 子集要求 点数互异，因此在任何“见证 \(S\in\mathcal{R}(C)\) 的子集 \(B\)”里，同一行最多贡献一张牌。 所以当我们从这一行选择了 \(A\) 时，它对可达集合族的作用只能是：

  • 原来可达的 \(S\) 仍然可达；
  • 另外可以把某个原可达的 \(S\) 扩张成 \(S\cup \{s\}\)，其中 \(s\in A\) 且 \(s\notin S\)（即使用这一行的一张牌，把匹配规模加 1）。

因此新的可达集合族满足集合递推：

\[\mathcal{R}'=\mathcal{R}\cup\{S\cup{s}\mid S\in\mathcal{R},s\in A,s\notin S\}.\tag{1}\]

注意右侧扩张用到的是 旧的 \(\mathcal{R}\)，而不是已经更新后的 \(\mathcal{R}'\)。这正对应“同一行不能链式扩张两次”：否则等价于在同一个点数上用两张牌参与匹配，违背点数互异。

把 \((1)\) 变成掩码更新，只需要定义一个行更新算子\(U_A:\{0,1\}^{16}\to \{0,1\}^{16}, M' = U_A(M),\) 它满足逐集合形式

\[ \mathbf 1[S\in\mathcal{R}']= \mathbf 1[S\in\mathcal{R}]\lor \bigvee_{s\in A}\mathbf 1[S\setminus\{s\}\in\mathcal{R}]. \tag{2} \]

这里 \(S\setminus\{s\}\) 表示从集合 \(S\) 中去掉元素 \(s\)（若 \(s\notin S\) 则该项恒为假）。因此，\((2)\) 就是 \((1)\) 的直接等价：要让 \(S\) 在更新后可达，要么它原本可达，要么存在 \(s\in A\) 使得去掉 \(s\) 的集合原本可达。

在行 \(r\to r+1\) 的推进中，我们枚举该行所选花色集合 \(A\subseteq\Sigma\)。因为每个花色最多选 1 张，所以一行的选择数就是 \(2^4=16\) 种。

于是对所有 \(r=0,1,\dots,12\)，所有 \(c=0,1,\dots,13\)，以及所有掩码 \(M\)，有转移：

\[ D_{r+1,c+|A|}(U_A(M))\leftarrow D_{r,c}(M),\tag{3} \]

其中，\(\forall A\subseteq\Sigma\land c+|A|\le 13\). \((3)\)这个式子的含义是：每一行独立选择 \(A\)，牌数增加 \(|A|\)，可达掩码按 \(U_A\) 更新。

令全花色集合为 \(\Sigma\)，其编码对应的掩码位记为 \([\Sigma]\)（即二进制 \(1111_2\) 那一位）。 包含一个 Badugi 子集等价于最终可达集合族包含 \(\Sigma\)，也就是最终掩码 \(M\) 的 \([\Sigma]\) 位为 \(1\)。

因此

\[ f(n)=\sum_{M:\text{bit}_{[\Sigma]}(M)=1} D_{13,n}(M), 4\le n\le 13. \tag{4} \]

最终代入计算\(\displaystyle{\sum_{n=4}^{13} f(n)}\)的值即可。

代码

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
from collections import defaultdict

if __name__ == "__main__":
    MAXN = 13
    FULL_SET_BIT = 1 << 15  # subset 1111 in the 16-bit mask-of-subsets

    # popcount for 4-bit masks
    pop = [x.bit_count() for x in range(16)]

    # For suit p, mask_zero[p] has bit S = 1 iff subset S does NOT contain p.
    mask_zero = []
    for p in range(4):
        m = 0
        for S in range(16):
            if ((S >> p) & 1) == 0:
                m |= 1 << S
        mask_zero.append(m)

    def upd(M: int, A: int) -> int:
        """
        Update reachability mask M after choosing suit subset A in the current rank(row).
        Important: expansions are based on the OLD M (no chaining within a row),
        because a matching can use at most one card from this rank.
        """
        M0 = M
        res = M0
        if A & 1:
            res |= (M0 & mask_zero[0]) << 1
        if A & 2:
            res |= (M0 & mask_zero[1]) << 2
        if A & 4:
            res |= (M0 & mask_zero[2]) << 4
        if A & 8:
            res |= (M0 & mask_zero[3]) << 8
        return res

    # dp[c] is a dict: key=M -> count
    dp = [defaultdict(int) for _ in range(MAXN + 1)]
    dp[0][1] = 1  # only empty subset reachable

    for _ in range(13):  # 13 ranks
        ndp = [defaultdict(int) for _ in range(MAXN + 1)]
        for c in range(MAXN + 1):
            if not dp[c]:
                continue
            for M, cnt in dp[c].items():
                for A in range(16):  # choose any subset of 4 suits in this rank
                    k = pop[A]
                    if c + k > MAXN:
                        continue
                    ndp[c + k][upd(M, A)] += cnt
        dp = ndp

    total = 0
    for n in range(4, 14):
        fn = sum(cnt for M, cnt in dp[n].items() if (M & FULL_SET_BIT))
        # 题面给的校验：f(5) 应为 514800
        # 你也可以打印出来对照：
        # print(n, fn)
        total += fn

    print(total)