给你一个字符串 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'。
统计平衡排列的数目
题目
给你一个字符串 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'。
题解
方法一:
思路
设$num$长度为$n$，$num$中数字总和为$s$，$nums$中数字$i$出现的次数为$c_i$
我们需要选取$C = \lfloor \frac{n}{2} \rfloor$个数字使得和为$V=\frac{s}{2}$
如果s是个奇数是没有答案的。
可以转化为背包计数问题，总共有10件物品，每件物品i最少选择0次，最多选择$c_i$次，容量1为$V$，背包容量2为$C$。每件物品i的体积1为i，体积2为1。
定义$f_{i,j,k}$为前i件物品中容量1恰好达到j，容量2恰好达到k的方案数。
对于合法方案的计算，共选择了C个物品，我们需要计算排列数$C!$，但是存在重复的物品，如果我们选择了物品i的$u_i$次，那么根据多重全排列，有$\frac{C!}{\prod u_i!}$种方案，对于剩下的没有选择的物品$\frac{(n-C)!}{\prod (c_i - u_i)!}$种方案，乘法原理得到方案数为$\frac{C!(n-C)!}{\prod u_i!(c_i - u_i)!}$。
$f_{i,j,k} = \sum \limits_{u=0}^{c_i} f_{i-1,j-i\cdot u,k-u}\frac{C!(n-C)!}{ u!(c_i - u)!}, j\ge i\cdot u , k\ge u$
恰好型背包，初始化$f_{0,0,0} = C!(n-C)!$
答案是$f_{10, V, C}$
预处理阶乘和阶乘逆元，阶乘逆元模质数可以基于费马小定理快速幂得到。
代码
1 | class Solution { |