2025-05-30：统计平衡排列的数目。用go语言，给定一个数字字符串 num，如果该字符串中所有位于奇数索引位置的数字之和与

package main

import (
    "fmt"
)

const MOD = 1_000_000_007

func countBalancedPermutations(num string)int {
    tot, n := 0, len(num)
    cnt := make([]int, 10)
    for _, ch := range num {
        d := int(ch - '0')
        cnt[d]++
        tot += d
    }
    if tot%2 != 0 {
        return0
    }

    target := tot / 2
    maxOdd := (n + 1) / 2
    comb := make([][]int, maxOdd+1)
    for i := range comb {
        comb[i] = make([]int, maxOdd+1)
        comb[i][i], comb[i][0] = 1, 1
        for j := 1; j < i; j++ {
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD
        }
    }

    f := make([][]int, target+1)
    for i := range f {
        f[i] = make([]int, maxOdd+1)
    }
    f[0][0] = 1

    psum, totSum := 0, 0
    for i := 0; i <= 9; i++ {
        /* 前 i 个数字的数目之和 */
        psum += cnt[i]
        /* 前 i 个数字的元素之和 */
        totSum += i * cnt[i]
        for oddCnt := min(psum, maxOdd); oddCnt >= max(0, psum-(n-maxOdd)); oddCnt-- {
            /* 偶数位需要填充的位数 */
            evenCnt := psum - oddCnt
            for curr := min(totSum, target); curr >= max(0, totSum-target); curr-- {
                res := 0
                for j := max(0, cnt[i]-evenCnt); j <= min(cnt[i], oddCnt) && i*j <= curr; j++ {
                    /* 当前数字在奇数位填充 j 位，偶数位填充 cnt[i] - j 位 */
                    ways := comb[oddCnt][j] * comb[evenCnt][cnt[i]-j] % MOD
                    res = (res + ways*f[curr-i*j][oddCnt-j]%MOD) % MOD
                }
                f[curr][oddCnt] = res % MOD
            }
        }
    }

    return f[target][maxOdd]
}

func main() {
    num := "123"
    result := countBalancedPermutations(num)
    fmt.Println(result)
}

# -*-coding:utf-8-*-

MOD = 10**9 + 7

defmin(a, b):
    return a if a < b else b

defmax(a, b):
    return a if a > b else b

defcountBalancedPermutations(num: str) -> int:
    tot = 0
    n = len(num)
    cnt = [0] * 10
    for ch in num:
        d = int(ch)
        cnt[d] += 1
        tot += d
    if tot % 2 != 0:
        return0

    target = tot // 2
    maxOdd = (n + 1) // 2

    # 计算组合数 comb[i][j] 表示 C(i, j)
    comb = [[0] * (maxOdd + 1) for _ inrange(maxOdd + 1)]
    for i inrange(maxOdd + 1):
        comb[i][0] = 1
        comb[i][i] = 1
        for j inrange(1, i):
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD

    # f[curr][oddCnt] 表示当前和为 curr，奇数位填充 oddCnt 个数字的方案数
    f = [[0] * (maxOdd + 1) for _ inrange(target + 1)]
    f[0][0] = 1

    psum = 0# cnt 的前缀和
    totSum = 0# 数字之和前缀和
    for i inrange(10):
        psum += cnt[i]
        totSum += i * cnt[i]

        oddCnt_start = max(0, psum - (n - maxOdd))
        oddCnt_end = min(psum, maxOdd)

        # 从大到小遍历避免重复计算覆盖
        for oddCnt inrange(oddCnt_end, oddCnt_start - 1, -1):
            evenCnt = psum - oddCnt
            curr_start = max(0, totSum - target)
            curr_end = min(totSum, target)
            for curr inrange(curr_end, curr_start - 1, -1):
                res = 0
                j_start = max(0, cnt[i] - evenCnt)
                j_end = min(cnt[i], oddCnt)
                for j inrange(j_start, j_end + 1):
                    if i * j > curr:
                        break
                    ways = comb[oddCnt][j] * comb[evenCnt][cnt[i] - j] % MOD
                    res = (res + ways * f[curr - i * j][oddCnt - j]) % MOD
                f[curr][oddCnt] = res

    return f[target][maxOdd]


if __name__ == "__main__":
    num = "123"
    result = countBalancedPermutations(num)
    print(result)