算法: 代表字母的整形数组组合字符串的可能性
问题描述 已知有一个长度为 26 的整型数组, 分别代表 26 个字母的个数, 问这些字母能组成多少种不同的字符串(取模 1000000007). 问题求解 纯暴力 开始觉得很简单, 纯迭代问题, 抬手就来. int calc(int[] nums) { int ret = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { nums[i]--; ret += calc(nums); ret %= 1000000007; nums[i]++; } } return ret > 0 ? ret : 1; } 结果超时, 不行, 看来只能用数学方法求解. 数学方法 $$ Sum=\dfrac{A_{字母总数}^{字母总数}}{A_{A的数量}^{A的数量}\times……\times A_{2}^{2}} $$ 题目没有讲太清楚(是否这些字母一定要全部使用), 这里为了简单就假设全部使用. 解法一：排列组合. 生成字符串长度是 $sum=a_0+a_1+a_2+…+a_{25}$. 放 $a$ , 有$(sum, a0)$种选择的方法; 放$ b$, 有$(sum - a0, a1)$种方法; 放 $c$, 有$(sum - a0 - a1, a2)$种方法…..直到最后 程序 private long solve1(int[] letters) { int sum = 0; for (int c : letters) { sum += c; } BigInteger r = BigInteger.ONE; for (int c : letters) { BigInteger s = choose(sum, c); r = r.multiply(s); sum -= c; } return r.longValue(); } private static BigInteger choose(int n, int k) { BigInteger r = BigInteger.ONE; for (int i=0; i<k; i++) { r = r.multiply(BigInteger.valueOf(n - i)); } for (int i=2; i<=k; i++) { r = r.divide(BigInteger.valueOf(i)); } return r; } 解法 2: EGF (指数生成函数)。 这是个排列问题所以用指数生成函数. ...