问题描述

已知有一个长度为 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 (指数生成函数)。

这是个排列问题所以用指数生成函数.

对于$a$: 有$ a_0$ 个$ a$ 要放.写成指数函数形式 $e_0=e^{(a_0)/a_0!}$ .

同样对于 $b$ : 有 $a_1$ 个 $b$ 要放。写成指数函数形式 $e_1=e^{(a_1)/a_1!}$ 等等等等 最后到 $z$ , 有 $a_{25}$ 个 z 要放，写成指数函数形式 $e_{25}=e^{(a_{25})/a_5!} $根据指数生成函数的理论，整个排列数就是 $E=e_0e_1…*e_{25}$

中项 $e^{(sum)/sum!}$ 的系数.

// Solve by GEF
private long solve2(int[] a) {
    int sum = 0;
    for (int c : a) {
    	sum += c;
    }
    BigInteger p = p(sum);
    BigInteger c = BigInteger.ONE;
    for (int i : a) {
    	c = c.multiply(p(i));
    }
    return p.divide(c).longValue();
}

private BigInteger p(int sum) {
    BigInteger r = BigInteger.ONE;
    for (int i= sum; i>=2; i--) {
        r = r.multiply(BigInteger.valueOf(i));
    }
    return r;
}

完毕.