LeetCode每日一题2025-05-09

点击获取AI摘要

3343. 统计平衡排列的数目 H

给你一个字符串 num 。如果一个数字字符串的奇数位下标的数字之和与偶数位下标的数字之和相等，那么我们称这个数字字符串是 平衡的 。

请你返回 num 不同排列 中，平衡 字符串的数目。

由于答案可能很大，请你将答案对 10⁹ + 7 取余 后返回。

一个字符串的 排列 指的是将字符串中的字符打乱顺序后连接得到的字符串。

示例 1：

输入： num = “123”

输出： 2

解释：

• num 的不同排列包括： "123" ，"132" ，"213" ，"231" ，"312" 和 "321" 。
• 它们之中，"132" 和 "231" 是平衡的。所以答案为 2 。

示例 2：

输入： num = “112”

输出： 1

解释：

• num 的不同排列包括："112" ，"121" 和 "211" 。
• 只有 "121" 是平衡的。所以答案为 1 。

示例 3：

输入： num = “12345”

**输出： ** 0

解释：

• num 的所有排列都是不平衡的。所以答案为 0 。

提示：

• 2 <= num.length <= 80
• num 中的字符只包含数字 '0' 到 '9' 。

问题分析

• 定义 ：给定字符串 num（长度 $2\le n\le80$，只包含字符 '0'–'9'），如果一个排列中奇数位下标（从 0 开始计数，则偶数位为奇数下标）数字之和等于偶数位下标数字之和，则称该排列“平衡”。
• 目标 ：统计所有不同排列中平衡排列的数量，结果对 $10^9+7$ 取模返回。

算法思路

1. 统计各数字出现次数
对 0–9 分别统计出现次数 $c_v$。

2. 确定位置分组

• 总长度 $n=\text{len}(num)$。

• 奇数位（下标 1,3,…）与偶数位（下标 0,2,…）的数量分别为

  $$m=\lceil n/2\rceil,\quad n-m=\lfloor n/2\rfloor.$$

3. 平衡条件
令总和 $S=\sum_{v}v\cdot c_v$，必须 $S$ 为偶数，否则返回 0。设目标子和$T=S/2.$

4. 生成函数 + 二维动态规划
构造多项式

$$P_v(t,z)=\sum_{x=0}^{c_v}\binom{c_v}{x}\,t^x\,z^{v\,x},$$

展开后，$[t^m,z^T]G(t,z)$ 即为所有合法“取法”之组合个数，内部已含 $\prod\binom{c_v}{x_v}$。

表示从数字 $v$ 中取 $x$ 个放入“奇数位”组的方式数。整体的生成函数乘积

$$G(t,z)=\prod_{v=0}^9P_v(t,z)$$

展开后，$[t^m,z^T]G(t,z)$ 即为所有合法“取法”之组合个数，内部已含 $\prod\binom{c_v}{x_v}$。

5. 排列计数
每一种“取法”将具体哪些位置放哪些相同数字还需排列：

• 奇数位内部可排列 $m!/\prod x_v!$ 种，偶数位内部 $(n-m)!/\prod(c_v-x_v)!$ 种。

• 但在生成函数里我们已包含 $\prod\binom{c_v}{x_v}=\prod\bigl(x_v! (c_v-x_v)!/c_v!\bigr)$ 的倒数部分，最终只需补上

  $$m!\,(n-m)! \,\Big/\prod c_v!\,$$

  其中 $\prod c_v!$ 与所有分配无关，是常数，可在结尾统一除去（或乘上其逆元）。

6. 实现细节

• 二维 dp[k][s] 表示考虑到某一位值时，已选入奇数位共 $k$ 个数字、累积和为 $s$ 的“取法”总数。

• 最终答案

  $$\text{dp}[m][T] \times m!\times(n-m)! \times \bigl(\prod_{v}c_v!\bigr)^{-1}\bmod(10^9+7).$$

时间复杂度

时间复杂度：$O(D \times m \times \tfrac{S}{2})$，其中 $D=10$ 为数字种类，$m\le40$，$\tfrac{S}{2}\le360$，整体约 $10^6$ 级别

空间复杂度：$O(m\times \tfrac{S}{2})$，约 $40\times360$

思路详解

1. 拆成“奇数位”和“偶数位”两组

• 我们把下标从 0 开始编号，那么下标为 0、2、4… 的叫“偶数位”，下标为 1、3、5… 的叫“奇数位”。
• 平衡的定义是：奇数位上数字之和 = 偶数位上数字之和。

例如，字符串 "132"：

• 偶数位：下标 0、2 → 数字 1 + 2 = 3
• 奇数位：下标 1 → 数字 3
  两者相等，所以 "132" 是平衡的。

2. 总和必须是偶数

• 所有数字相加得到总和 S，如果 S 是奇数，就不可能一分为二所以直接返回 0。

3. 分组大小 m

• 设字符串长度为 n：
  • 偶数位数量 = ⌊n/2⌋
  • 奇数位数量 = ⌈n/2⌉，我们记为 m。

例如 n=3 时，偶数位有 2（下标 0、2），奇数位有 1（下标 1），所以 m = 1。

4. 把“选择哪些数字放到奇数位”当成背包问题

我们需要从原字符串里的每个数字（例如可能有三个 1、两个 2、一个 3……）中，决定放多少个到“奇数位”这 m 个位置上，剩下的放到“偶数位”。

• 对于每个数字 v（0～9），假设它出现了 $c_v$ 次，我们可以选择 x 个放到奇数位，x 的范围是 0…$c_v$，但总共所有数字放到奇数位的个数要刚好是 m。
• 同时，奇数位上数字的和 = 偶数位上数字的和 = S/2。由于奇数位和 + 偶数位和 = S，那么每边都要是 S/2。

于是，我们要计算：对每个 v，从 $c_v$ 中选 $x_v$，使得

1. $\sum_v x_v = m$
2. $\sum_v (v \times x_v) = S/2$

满足以上两个条件的所有组合数，就是“把具体哪些数字拿到奇数位”的方法数。最后再把数字在奇数位内部、偶数位内部的排列数乘进去，就是完整的排列。

用二维动态规划 dp[k][s]

• 定义：dp[k][s] = “考虑了数字 0…v 时，已选了 k 个数字放在奇数位，且它们的和为 s 的方法数”。
• 初始化 dp[0][0] = 1（还没放任何数字，个数 0，和 0 有 1 种办法）。
• 递推：对下一个数字 v，共有 $c_v$ 个，枚举 $x=0\cdots \min(c_v, m-k)$（即本轮还不能超出 m），如果之前状态是 dp[k][s]，放 x 个到奇数位后，变成 dp[k+x][s+v*x]，方法数累加。

最终看 dp[m][S/2]，就是所有满足分组大小和目标和的分配数。

5. 乘上阶乘再除以出现次数的阶乘

前面 dp 只算了“选哪些数字放到奇数位”，但一个具体的分配（比如放了两个 1、一个 4……）在奇数位这 m 个位置内部还可以排列；同样偶数位也可以排列。

• 奇数位内部排列数：m! ÷ (每个数字在奇数位放入的次数! 的乘积)
• 偶数位内部排列数：(n−m)! ÷ (每个数字剩余次数! 的乘积)

而在 dp 转移里我们已经用组合数 $C(c_v, x) = \frac{c_v!}{x! (c_v - x)!}$ 来考虑了“从 $c_v$ 个里选 x 个”的方法（含了 $x!$、$(c_v−x)!$ 的分母）。综合起来，最后直接把

dp[m][half] 
× m!         （奇数位内部全排列）
× (n−m)!     （偶数位内部全排列）
× Π_v (c_v!)⁻¹  （把之前组合计算中分母的 c_v! 抵消）
mod 1e9+7

就得到了完整的排列数。

代码实现

class Solution:
    MOD = 10**9 + 7

    def countBalancedPermutations(self, num: str) -> int:
        # 中间变量
        velunexorai = num
        lomiktrayve = velunexorai

        n = len(lomiktrayve)
        # 分组大小
        m = (n + 1) // 2  # 奇数位数量
        # 统计各数字出现次数
        cnt = [0] * 10
        for ch in lomiktrayve:
            cnt[ord(ch) - ord('0')] += 1

        # 总和及平衡目标
        S = sum(v * cnt[v] for v in range(10))
        if S & 1:  # 奇数和，不可能平衡
            return 0
        half = S // 2

        # 预处理阶乘及逆元
        maxfact = n
        fact = [1] * (maxfact + 1)
        inv_fact = [1] * (maxfact + 1)
        for i in range(1, maxfact + 1):
            fact[i] = fact[i-1] * i % self.MOD
        inv_fact[maxfact] = pow(fact[maxfact], self.MOD-2, self.MOD)
        for i in range(maxfact, 0, -1):
            inv_fact[i-1] = inv_fact[i] * i % self.MOD

        # dp[k][s]: 考虑前 v 数字后，选入奇数位共 k 个，累积和 s 的方式数
        dp = [[0] * (half + 1) for _ in range(m + 1)]
        dp[0][0] = 1

        # 转移：对每个数字 v，枚举放入奇数位 x 个
        for v in range(10):
            c = cnt[v]
            # 预计算 C(c, x) * (c-x)!^-1 * x!^-1 里的一部分：C(c,x)
            comb = [0] * (c + 1)
            for x in range(c + 1):
                comb[x] = fact[c] * inv_fact[x] % self.MOD * inv_fact[c-x] % self.MOD

            new_dp = [[0] * (half + 1) for _ in range(m + 1)]
            for k in range(m+1):
                for s in range(half+1):
                    if dp[k][s] == 0:
                        continue
                    base = dp[k][s]
                    # 放 x 个到奇数位
                    for x in range(min(c, m-k) + 1):
                        ns = s + v * x
                        if ns > half:
                            break
                        new_dp[k + x][ns] = (new_dp[k + x][ns] + base * comb[x]) % self.MOD
            dp = new_dp

        ways = dp[m][half]
        if ways == 0:
            return 0

        # 最终乘上 m!*(n-m)!，并除以 ∏c_v!（即乘上每个 c_v! 的逆元）
        ans = ways * fact[m] % self.MOD * fact[n-m] % self.MOD
        for v in range(10):
            ans = ans * inv_fact[cnt[v]] % self.MOD
        return ans

以num = "112"为例：

1. n=3，m=⌈3/2⌉=2，S=1+1+2=4，half=2。
2. 数字计数：cnt[1]=2，cnt[2]=1，其他都是 0。
3. dp 大小是 (m+1=3)×(half+1=3)。
4. 先处理 v=1，c=2，可以放 x=0,1,2 个到奇数位；再处理 v=2，c=1，可放 x=0,1。
5. 通过 dp 最终找到 dp[2][2] = 1，表示把恰好 2 个数字放到奇数位，且它们和为 2 的方法只有 1 种（就是放两个 1）。
6. 乘上 m!×(n–m)! ÷ (2!×1!) = 2!×1! ÷ (2!×1!) = 1，结果仍是 1。

也就是说，只有排列 "121" 是平衡的。