计数字谜时如何避免溢出？
How to avoid overflow when counting anagrams?
令 N 为字符串的大小。令 A、B、C...、Z 为每个字母在字符串中出现的次数。
我需要计算字谜的数量：N!/(A!*B!*C!...*Z!)。
确保最终结果适合一个整数，但原始字符串的长度可以是任意大小。
到目前为止，我唯一的想法是对乘积中的数字进行质因数分解，然后消除分母中也存在的分子因子。
有没有更实用的方法来实现？
为 N 的素数因子创建一个映射，其中键是一个 int（素数因子），值是计数。
为 N.
做这张地图
say, N = 10
factors = 2 x 5
map[2] = 1
map[5] = 1
然后遍历像 A,B,...Z 这样的计数并找到质因数并从上面的地图中减少计数
say A= 5, factors= 5 x1
//just mark
map[5] = 1-1 = 0
similarly, for B....Z
现在给出答案，从最大素数开始遍历map，如果值为正则继续乘以键，如果值为负则继续除以键。
tmp = 5 , //largest prime factor
result = 1
for(int i=tmp;i>1;i--) {
if(map[tmp]>0) {
result = result * tmp * map[tmp];
} else if( map[tmp]<0) {
result = result / (tmp * map[tmp] * -1);`
}
}
print(result)
我找到了一个使用 2 个数组的解决方案，每个部分都有乘法项。使用 GCD 简化术语。这是我的 C++ 代码：（映射具有字符及其各自的频率）。
unsigned int fatnk(int n, map<char, int> &k)
{
vector<int> numerator, denominator;
for (int i = 2; i <= n; i++)
numerator.push_back(i);
for (auto it : k)
if (it.second > 1)
for (int i = 2; i <= it.second; i++)
denominator.push_back(i);
for (int i = 0; i < numerator.size(); i++)
for (int j = 0; numerator[i] > 1 && j < denominator.size(); j++)
{
if (denominator[j] == 1)
continue;
int d = gcd(numerator[i], denominator[j]);
if (d == 1)
continue;
numerator[i] /= d;
denominator[j] /= d;
}
unsigned int ans = 1;
for (auto it : numerator)
ans *= it;
return ans;
}
您可以通过交叉乘法和除法来进行计算，而不是先进行所有分子乘法，然后除以所有除数。交错操作显着减小了中间值的大小，但它并不能完全保证没有中间结果会大于最终结果。稍加努力，我们可以找到一个乘法和除法的顺序，其中除法总是精确的，并且没有中间结果超过最终结果。 （如果您不关心解释，请跳至此答案底部的示例代码。）
了解交错乘法和除法的工作原理很有用。为了使除法精确，除法之前的中间值必须是除数的精确倍数。在这种情况下，这是真的，因为乘数是一个稳定增加的整数序列。
这是一个简单的交错示例，只有两个字母。我们要计算 (7 C 5)，这是 aaaaabb 的字谜数。 （它也是一个二项式系数，因为它与询问长度为 7 的列表中 5 个位置的组数相同。我们可以通过在所选的五个位置放置 as 来构建唯一的变位词，并且 bs 在另外两个中。）所以天真的计算是：
1 ×2 ×3 ×4 ×5 ×6 ×7 ÷1 ÷2 ÷3 ÷4 ÷5 ÷1 ÷2
1 2 6 24 120 720 5040 5040 2520 840 210 42 42 21
最大的中间值是 5040。这不是溢出（除非我们使用 8 位算术）但它比需要的大很多。这是交错选项：
1 ÷1 ×2 ÷2 ×3 ÷3 ×4 ÷4 ×5 ÷5 ×6 ÷1 ×7 ÷2
1 1 2 1 3 1 4 1 5 1 6 6 42 21
现在，最大的中间结果是42，甚至不会溢出char。如果我们除以 2，我们会得到相同的结果！首先，而不是从 5 开始！:
1 ÷1 ×2 ÷2 ×3 ÷1 ×4 ÷2 ×5 ÷3 ×6 ÷4 ×7 ÷5
1 1 2 1 3 3 12 6 30 10 60 15 105 21
按照这个顺序，有更多的中间值超过了最终结果，但最大的仍然没有接近原来的5040。
很明显，在上述两种情况下，除法都是准确的，但为什么一定是这样可能不是很明显。证明（使用归纳法）并不难，但直观的解释也不是很复杂。考虑上面第二个例子中的（最终）除以 5。在这个简单的例子中，之前没有除以因子为 5 的被除数，而且之前肯定有乘以 5 的倍数，所以除法是准确的也就不足为奇了。
但假设之前有过5的倍数除法，如果是这样，那次除法肯定是很久以前的，因为前面4次除法都是小于5的数。换句话说，在我们除以 p 的任何点，前面除以 p 的倍数之前必须至少有 p 个连续整数的乘法。其中一个乘法一定是 p 的倍数，因为每个 p 整数都有 p 的倍数。由于自乘法以来没有被 p 除法，我们可以相信 p 仍然是累加结果的一部分，因此被 p 的除法是安全的。
除法之后的中间结果单调递增也很容易看出。那是因为在 multiply/divide 序列中，乘数必须大于除数；乘数只是一个递增的序列，而除数周期性地重置为 1。这反过来意味着最大的中间值不能大于最大除数乘以最终结果。因此，如果我们可以使用稍宽的整数类型进行中间计算，就可以避免溢出。这可能是一个足够好的解决方案，但最终结果可能被允许为语言的最大整数类型，在这种情况下，中间计算没有更宽的类型。我们需要更好的保障。
所以让我们return解释为什么当我们要除以p时我们知道中间值可以被p整除。关键是最近的p次乘法中肯定有p次乘法。现在，考虑两种可能性：
- 最后一次乘法是
p的倍数。
- 最后一次乘法不是
p的倍数。
在情况2中，最后一次乘法之前的中间值已经有p作为因数，所以我们可以先做除法。在情况 1 中，最后一次乘法本身是 p 的某个倍数，因此我们可以在乘法之前将乘数除以 p。很容易知道我们正在查看的是这两种情况中的哪一种，只需用除数对乘数进行试相除法即可。通过该修改，我们保证没有中间结果大于最终结果，因此如果最终结果是可表示的，则溢出是不可能的。
这是一个简单的 C 实现。各种优化是可能的le，但我尽量保持简单；因为它的执行时间通常以微秒为单位：
long long count_anagrams(int n, int letters[26]) {
long long count = 1;
for (int mult = 1, divisor = 1, letter = 0; mult <= n; ++mult, ++divisor) {
while (divisor > letters[letter]) {
++letter;
divisor = 1;
}
if (mult % divisor == 0)
count *= mult / divisor;
else {
count /= divisor;
count *= mult;
}
}
return count;
}
一个测试用例，针对使用 bignums 的简单 Python 程序进行验证：
$ ./anagrams abcdddddddddddddddddddddddddddeeeeeffffggg
There are 7467095163297369600 anagrams of abcdddddddddddddddddddddddddddeeeeeffffggg
您不需要单独分解数字。只需分解 1..n 范围内所有内容的乘积。那是一个 O(n log(log(n))) 操作。然后你就可以取消了。
这是 Python 的：
def factor_range(n):
is_prime = [True for i in range(n+1)]
factorization = {}
for p in range(2, n+1):
if is_prime[p]:
power = p
factors = 0
while power <= n:
s = power
while s <= n:
factors = factors + 1
is_prime[s] = 0
s = s + power
power = power * p
factorization[p] = factors
return factorization
（在我的笔记本电脑上，这能够在一秒钟内给出 1000000 的完全分解版本！）
令 N 为字符串的大小。令 A、B、C...、Z 为每个字母在字符串中出现的次数。
我需要计算字谜的数量：N!/(A!*B!*C!...*Z!)。
确保最终结果适合一个整数，但原始字符串的长度可以是任意大小。
到目前为止，我唯一的想法是对乘积中的数字进行质因数分解，然后消除分母中也存在的分子因子。
有没有更实用的方法来实现？
为 N 的素数因子创建一个映射，其中键是一个 int（素数因子），值是计数。 为 N.
做这张地图say, N = 10
factors = 2 x 5
map[2] = 1
map[5] = 1
然后遍历像 A,B,...Z 这样的计数并找到质因数并从上面的地图中减少计数
say A= 5, factors= 5 x1
//just mark
map[5] = 1-1 = 0
similarly, for B....Z
现在给出答案，从最大素数开始遍历map，如果值为正则继续乘以键，如果值为负则继续除以键。
tmp = 5 , //largest prime factor
result = 1
for(int i=tmp;i>1;i--) {
if(map[tmp]>0) {
result = result * tmp * map[tmp];
} else if( map[tmp]<0) {
result = result / (tmp * map[tmp] * -1);`
}
}
print(result)
我找到了一个使用 2 个数组的解决方案，每个部分都有乘法项。使用 GCD 简化术语。这是我的 C++ 代码：（映射具有字符及其各自的频率）。
unsigned int fatnk(int n, map<char, int> &k)
{
vector<int> numerator, denominator;
for (int i = 2; i <= n; i++)
numerator.push_back(i);
for (auto it : k)
if (it.second > 1)
for (int i = 2; i <= it.second; i++)
denominator.push_back(i);
for (int i = 0; i < numerator.size(); i++)
for (int j = 0; numerator[i] > 1 && j < denominator.size(); j++)
{
if (denominator[j] == 1)
continue;
int d = gcd(numerator[i], denominator[j]);
if (d == 1)
continue;
numerator[i] /= d;
denominator[j] /= d;
}
unsigned int ans = 1;
for (auto it : numerator)
ans *= it;
return ans;
}
您可以通过交叉乘法和除法来进行计算，而不是先进行所有分子乘法，然后除以所有除数。交错操作显着减小了中间值的大小，但它并不能完全保证没有中间结果会大于最终结果。稍加努力，我们可以找到一个乘法和除法的顺序，其中除法总是精确的，并且没有中间结果超过最终结果。 （如果您不关心解释，请跳至此答案底部的示例代码。）
了解交错乘法和除法的工作原理很有用。为了使除法精确，除法之前的中间值必须是除数的精确倍数。在这种情况下，这是真的，因为乘数是一个稳定增加的整数序列。
这是一个简单的交错示例，只有两个字母。我们要计算 (7 C 5)，这是 aaaaabb 的字谜数。 （它也是一个二项式系数，因为它与询问长度为 7 的列表中 5 个位置的组数相同。我们可以通过在所选的五个位置放置 as 来构建唯一的变位词，并且 bs 在另外两个中。）所以天真的计算是：
1 ×2 ×3 ×4 ×5 ×6 ×7 ÷1 ÷2 ÷3 ÷4 ÷5 ÷1 ÷2
1 2 6 24 120 720 5040 5040 2520 840 210 42 42 21
最大的中间值是 5040。这不是溢出（除非我们使用 8 位算术）但它比需要的大很多。这是交错选项：
1 ÷1 ×2 ÷2 ×3 ÷3 ×4 ÷4 ×5 ÷5 ×6 ÷1 ×7 ÷2
1 1 2 1 3 1 4 1 5 1 6 6 42 21
现在，最大的中间结果是42，甚至不会溢出char。如果我们除以 2，我们会得到相同的结果！首先，而不是从 5 开始！:
1 ÷1 ×2 ÷2 ×3 ÷1 ×4 ÷2 ×5 ÷3 ×6 ÷4 ×7 ÷5
1 1 2 1 3 3 12 6 30 10 60 15 105 21
按照这个顺序，有更多的中间值超过了最终结果，但最大的仍然没有接近原来的5040。
很明显，在上述两种情况下，除法都是准确的，但为什么一定是这样可能不是很明显。证明（使用归纳法）并不难，但直观的解释也不是很复杂。考虑上面第二个例子中的（最终）除以 5。在这个简单的例子中，之前没有除以因子为 5 的被除数，而且之前肯定有乘以 5 的倍数，所以除法是准确的也就不足为奇了。
但假设之前有过5的倍数除法，如果是这样，那次除法肯定是很久以前的，因为前面4次除法都是小于5的数。换句话说，在我们除以 p 的任何点，前面除以 p 的倍数之前必须至少有 p 个连续整数的乘法。其中一个乘法一定是 p 的倍数，因为每个 p 整数都有 p 的倍数。由于自乘法以来没有被 p 除法，我们可以相信 p 仍然是累加结果的一部分，因此被 p 的除法是安全的。
除法之后的中间结果单调递增也很容易看出。那是因为在 multiply/divide 序列中，乘数必须大于除数；乘数只是一个递增的序列，而除数周期性地重置为 1。这反过来意味着最大的中间值不能大于最大除数乘以最终结果。因此，如果我们可以使用稍宽的整数类型进行中间计算，就可以避免溢出。这可能是一个足够好的解决方案，但最终结果可能被允许为语言的最大整数类型，在这种情况下，中间计算没有更宽的类型。我们需要更好的保障。
所以让我们return解释为什么当我们要除以p时我们知道中间值可以被p整除。关键是最近的p次乘法中肯定有p次乘法。现在，考虑两种可能性：
- 最后一次乘法是
p的倍数。 - 最后一次乘法不是
p的倍数。
在情况2中，最后一次乘法之前的中间值已经有p作为因数，所以我们可以先做除法。在情况 1 中，最后一次乘法本身是 p 的某个倍数，因此我们可以在乘法之前将乘数除以 p。很容易知道我们正在查看的是这两种情况中的哪一种，只需用除数对乘数进行试相除法即可。通过该修改，我们保证没有中间结果大于最终结果，因此如果最终结果是可表示的，则溢出是不可能的。
这是一个简单的 C 实现。各种优化是可能的le，但我尽量保持简单；因为它的执行时间通常以微秒为单位：
long long count_anagrams(int n, int letters[26]) {
long long count = 1;
for (int mult = 1, divisor = 1, letter = 0; mult <= n; ++mult, ++divisor) {
while (divisor > letters[letter]) {
++letter;
divisor = 1;
}
if (mult % divisor == 0)
count *= mult / divisor;
else {
count /= divisor;
count *= mult;
}
}
return count;
}
一个测试用例，针对使用 bignums 的简单 Python 程序进行验证：
$ ./anagrams abcdddddddddddddddddddddddddddeeeeeffffggg
There are 7467095163297369600 anagrams of abcdddddddddddddddddddddddddddeeeeeffffggg
您不需要单独分解数字。只需分解 1..n 范围内所有内容的乘积。那是一个 O(n log(log(n))) 操作。然后你就可以取消了。
这是 Python 的：
def factor_range(n):
is_prime = [True for i in range(n+1)]
factorization = {}
for p in range(2, n+1):
if is_prime[p]:
power = p
factors = 0
while power <= n:
s = power
while s <= n:
factors = factors + 1
is_prime[s] = 0
s = s + power
power = power * p
factorization[p] = factors
return factorization
（在我的笔记本电脑上，这能够在一秒钟内给出 1000000 的完全分解版本！）