脑子突然不好使了，请各位大佬帮我想想这个算法

[lihongming]

已知有一个长度为 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;
}

结果效率太差，不行。

我又想用数学的方法直接算，可脑子怎么也想不起该怎么算了，求大佬们指点。

[xuanbg]

2^32^26

[lihongming]

想起来了，应该是各数之和的阶乘除以各数的阶乘
(A + B + C + ...)! / (A! * B! * C! * ...)

[git00ll]

楼主这题哪里做的，能发下链接吗

[lff0305]

数学方式直接算：应该是指数生成函数

[crackhopper]

进一步优化，还需要找到 k!>i*1000000007 的对可以每个出现的 i，最小的 k 。可以快速简化计算。

[crackhopper]

刚才没考虑，还有除数，比较麻烦。当我之前没说

[flowfire]

这不是排列组合吗。。。
答案是（假设 a-z 分别代表各个字母的数量，大写 S 代表所有字母总数）：
A(S,S) / (A(a,a) * A(b,b) * ...... * A(z,z))

[flowfire]

贴张图：
https://s1.ax1x.com/2020/09/07/wuayLQ.jpg

[guonaihong]

对这个问题感兴趣。这些字母是否是互斥事件吗？比如第一位是 26 种可能，互斥的话，第二种是 25 种可能。
我的理解，根据条件有 2 种解 一种，26 * 26 ....n，即 26 的 26 次方。二种是后者就是 26!。
如果是组合的话，就是把重复计算的除掉 m 种取 n 种 =m!/(m-n)!n!。

[lff0305]

简单写了个程序。题目没有讲太清楚（是否这些字母一定要全部使用）。这里为了简单就假设全部使用。

解法一：排列组合。生成字符串长度是 sum=a0+a1+a2+...+a25 。放 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));
}

// System.out.println(n + "," + k + " = " + r);
return r;
}


解法 2: GEF (指数生成函数)。这是个排列问题所以用指数生成函数。
对于 a: 有 a0 个 a 要放。写成指数函数形式 e0=e^(a0)/a0!
同样对于 b: 有 a1 个 b 要放。写成指数函数形式 e1=e^(a1)/a1!
等等等等
最后到 z, 有 a25 个 z 要放，写成指数函数形式 e25=e^(a25)/a5!

根据指数生成函数的理论，整个排列数就是
E=e0*e1*...*e25，中项 e^(sum)/sum! 的系数。

那么 E=[e^(a0)/a0!][e^(a1)/a1!]*...*[e25=e^(a25)/a25!]
= [e^(a0+a1+...+a25)]/[a0!*a1!*...*a25!]
= [e^sum]/[a0!*a1!*...*a25!]
e ^ sum sum ！
= --------------------------- * --------------------
a0! *a1!* ... * a25 !) sum!

e ^ sum sum ！
= --------------------------- * --------------------------
sum! a0! *a1!* ... * a25 !

要求的系数就是 （ sum!)/( a0! *a1!* ... * a25 ! )

写成程序就是


// Solve by GEF
private long solve2(int[] a) {
// expr e0 = e^a0/a0!, e1 = e^a1/a1! ... etc
// E = e0*e1*e2 .... * e25
// e^(a0+a1+...+a25)/(a0!*a1*a2*....*a25!)
// ? = e^(a0 + a1 + ... + a25)/(sum!)
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;
}

[lff0305]

排版乱了， 重新弄下

简单写了个程序。题目没有讲太清楚（是否这些字母一定要全部使用）。这里为了简单就假设全部使用。

解法一：排列组合。生成字符串长度是 sum=a0+a1+a2+...+a25 。放 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));
}

// System.out.println(n + "," + k + " = " + r);
return r;
}

```
解法 2: GEF (指数生成函数)。这是个排列问题所以用指数生成函数。
对于 a: 有 a0 个 a 要放。写成指数函数形式 e0=e^(a0)/a0!
同样对于 b: 有 a1 个 b 要放。写成指数函数形式 e1=e^(a1)/a1!
等等等等
最后到 z, 有 a25 个 z 要放，写成指数函数形式 e25=e^(a25)/a5!

根据指数生成函数的理论，整个排列数就是
E=e0*e1*...*e25，中项 e^(sum)/sum! 的系数。

那么
```
E=[e^(a0)/a0!][e^(a1)/a1!]*...*[e25=e^(a25)/a25!]
= [e^(a0+a1+...+a25)]/[a0!*a1!*...*a25!]
= [e^sum]/[a0!*a1!*...*a25!]
e ^ sum sum ！
= --------------------------- * --------------------
a0! *a1!* ... * a25 !) sum!

e ^ sum sum ！
= --------------------------- * --------------------------
sum! a0! *a1!* ... * a25 !
```
要求的系数就是 （ sum!)/( a0! *a1!* ... * a25 ! )

写成程序就是

```
// Solve by GEF
private long solve2(int[] a) {
// expr e0 = e^a0/a0!, e1 = e^a1/a1! ... etc
// E = e0*e1*e2 .... * e25
// e^(a0+a1+...+a25)/(a0!*a1*a2*....*a25!)
// ? = e^(a0 + a1 + ... + a25)/(sum!)
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;
}
```

[QingchuanZhang]

@lff0305 EGF 。。。

[lihongming]

@guonaihong 是的，要全用上。比如给你 2 个 a 和 2 个 b，那么能组成 aabb, abab, abba, baab, baba, bbaa 六种字符串

[waruqi]

不就是 26 进制的 26 位数累加迭代么，直接用个 uint64 累加遍历么，然后将每个 10 进制数转成 26 进制，按每位映射到对应字母就好了，迭代到 26 位后结束，uint64 不够 就换 uint128 uint256

[toaruScar]

难道这个不是基础的 permutations with pepetitions 吗？

[no1xsyzy]

@lihongming @flowfire @lff0305 @toaruScar 问题是，整除是不是模数空间上的群？
当然，拿 BigInt 之类做归做，效率是问题。

@waruqi uint32 遍历需要大约 42 秒
uint64 已经要遍历到天荒地老。
怎么会想到遍历的，服（

[no1xsyzy]

简单重排一下的话
(A + B + C + ...)! / (A! * B! * C! * ...)
其实等于
A!/A! * ((A+B)!/A!/B!) * ((A+B+C)!/(A+B)!/C!) * ...
每块都是整数。

[flowfire]

@no1xsyzy #17 你这算法跟我的不一样吗。。。无非是表达方法不同罢了。。。

A(m,m) 就是 m! 啊。。。。

[toaruScar]

@flowfire #18 @no1xsyzy 的意思是，题目最后一步要求 mod，那不如就直接在 mod 的空间里计算。就是每步运算之后都去来个 mod，这样数字能小一点。然而 mod 空间里只有加减乘能用，也就是
( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
( a – b) % c = ( ( a % c ) – ( b % c ) ) % c
而( a / b) % c 是没有这个性质的
重排一下发现可以相消，于是分母都是 1，也就是只剩下乘法了。

[no1xsyzy]

刚地铁上突然意识到一点，整除有可能是模数空间上的群，因为给定整除，采用启发式算法的话，可能可行……
等我稍微写写 test 一下

[no1xsyzy]

竟然是可以的…… 之前拍脑袋了
已知整除的话，整除是模数空间上的群……
那没关系了，用模数空间上的整除做就行了。

[no1xsyzy]

参考： https://www.geeksforgeeks.org/modular-division/