class Solution {
public:
int countBalancedPermutations(string num) {
}
};
3343. 统计平衡排列的数目
给你一个字符串 num 。如果一个数字字符串的奇数位下标的数字之和与偶数位下标的数字之和相等，那么我们称这个数字字符串是 平衡的 。
请你返回 num 不同排列 中，平衡 字符串的数目。
由于答案可能很大，请你将答案对 109 + 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 <= 80num 中的字符只包含数字 '0' 到 '9' 。原站题解
java 解法, 执行用时: 59 ms, 内存消耗: 43.9 MB, 提交时间: 2024-11-17 23:39:36
class Solution {
private static final int MOD = 1_000_000_007;
private static final int MX = 41;
private static final long[] F = new long[MX]; // f[i] = i!
private static final long[] INV_F = new long[MX]; // inv_f[i] = i!^-1
static {
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i > 0; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
}
}
public int countBalancedPermutations(String num) {
int[] cnt = new int[10];
int total = 0;
for (char c : num.toCharArray()) {
cnt[c - '0']++;
total += c - '0';
}
if (total % 2 > 0) {
return 0;
}
int n = num.length();
int n1 = n / 2;
int[][] f = new int[n1 + 1][total / 2 + 1];
f[0][0] = 1;
int sc = 0;
int s = 0;
for (int i = 0; i < 10; i++) {
int c = cnt[i];
sc += c;
s += c * i;
// 保证 left2 <= n-n1，即 left1 >= sc-(n-n1)
for (int left1 = Math.min(sc, n1); left1 >= Math.max(sc - (n - n1), 0); left1--) {
int left2 = sc - left1;
// 保证分给第二个集合的元素和 <= total/2，即 leftS >= s-total/2
for (int leftS = Math.min(s, total / 2); leftS >= Math.max(s - total / 2, 0); leftS--) {
long res = 0;
for (int k = Math.max(c - left2, 0); k <= Math.min(c, left1) && k * i <= leftS; k++) {
res = (res + f[left1 - k][leftS - k * i] * INV_F[k] % MOD * INV_F[c - k]) % MOD;
}
f[left1][leftS] = (int) res;
}
}
}
return (int) (F[n1] * F[n - n1] % MOD * f[n1][total / 2] % MOD);
}
private static long pow(long x, int n) {
long res = 1;
for (; n > 0; n /= 2) {
if (n % 2 > 0) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}
}
golang 解法, 执行用时: 39 ms, 内存消耗: 8.1 MB, 提交时间: 2024-11-17 23:39:17
const mod = 1_000_000_007
const mx = 40
var fac, invF [mx + 1]int
func init() {
fac[0] = 1
for i := 1; i <= mx; i++ {
fac[i] = fac[i-1] * i % mod
}
invF[mx] = pow(fac[mx], mod-2)
for i := mx; i > 0; i-- {
invF[i-1] = invF[i] * i % mod
}
}
func countBalancedPermutations(num string) int {
cnt := [10]int{}
total := 0
for _, c := range num {
cnt[c-'0']++
total += int(c - '0')
}
if total%2 > 0 {
return 0
}
n := len(num)
n1 := n / 2
f := make([][]int, n1+1)
for i := range f {
f[i] = make([]int, total/2+1)
}
f[0][0] = 1
sc := 0
s := 0
for i, c := range cnt {
sc += c
s += c * i
// 保证 left2 <= n-n1，即 left1 >= sc-(n-n1)
for left1 := min(sc, n1); left1 >= max(sc-(n-n1), 0); left1-- {
left2 := sc - left1
// 保证分给第二个集合的元素和 <= total/2，即 leftS >= s-total/2
for leftS := min(s, total/2); leftS >= max(s-total/2, 0); leftS-- {
res := 0
for k := max(c-left2, 0); k <= min(c, left1) && k*i <= leftS; k++ {
res = (res + f[left1-k][leftS-k*i]*invF[k]%mod*invF[c-k]) % mod
}
f[left1][leftS] = res
}
}
}
return fac[n1] * fac[n-n1] % mod * f[n1][total/2] % mod
}
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
python3 解法, 执行用时: 1483 ms, 内存消耗: 17.1 MB, 提交时间: 2024-11-17 23:39:01
MOD = 1_000_000_007
MX = 41
fac = [0] * MX # f[i] = i!
fac[0] = 1
for i in range(1, MX):
fac[i] = fac[i - 1] * i % MOD
inv_f = [0] * MX # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
inv_f[i - 1] = inv_f[i] * i % MOD
class Solution:
def countBalancedPermutations(self, num: str) -> int:
cnt = [0] * 10
total = 0
for c in map(int, num):
cnt[c] += 1
total += c
if total % 2:
return 0
n = len(num)
n1 = n // 2
f = [[0] * (total // 2 + 1) for _ in range(n1 + 1)]
f[0][0] = 1
sc = s = 0
for i, c in enumerate(cnt):
sc += c
s += c * i
# 保证 left2 <= n-n1，即 left1 >= sc-(n-n1)
for left1 in range(min(sc, n1), max(sc - (n - n1) - 1, -1), -1):
left2 = sc - left1
# 保证分给第二个集合的元素和 <= total/2，即 left_s >= s-total/2
for left_s in range(min(s, total // 2), max(s - total // 2 - 1, -1), -1):
res = 0
for k in range(max(c - left2, 0), min(c, left1) + 1):
if k * i > left_s:
break
res += f[left1 - k][left_s - k * i] * inv_f[k] * inv_f[c - k]
f[left1][left_s] = res % MOD
return fac[n1] * fac[n - n1] * f[n1][total // 2] % MOD
python3 解法, 执行用时: 679 ms, 内存消耗: 36.4 MB, 提交时间: 2024-11-17 23:38:44
MOD = 1_000_000_007
MX = 41
fac = [0] * MX # f[i] = i!
fac[0] = 1
for i in range(1, MX):
fac[i] = fac[i - 1] * i % MOD
inv_f = [0] * MX # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
inv_f[i - 1] = inv_f[i] * i % MOD
class Solution:
def countBalancedPermutations(self, num: str) -> int:
cnt = [0] * 10
total = 0
for c in map(int, num):
cnt[c] += 1
total += c
if total % 2:
return 0
pre = list(accumulate(cnt))
@cache
def dfs(i: int, left1: int, left_s: int) -> int:
if i < 0:
return 1 if left_s == 0 else 0
res = 0
c = cnt[i]
left2 = pre[i] - left1
for k in range(max(c - left2, 0), min(c, left1) + 1):
if k * i > left_s:
break
r = dfs(i - 1, left1 - k, left_s - k * i)
res += r * inv_f[k] * inv_f[c - k]
return res % MOD
n = len(num)
n1 = n // 2
return fac[n1] * fac[n - n1] * dfs(9, n1, total // 2) % MOD