简单写了个程序。题目没有讲太清楚(是否这些字母一定要全部使用)。这里为了简单就假设全部使用。
解法一:排列组合。生成字符串长度是 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;
}