网格中的矩形总数？

Question

这里我想统计M*N个网格中矩形的总数。此代码工作正常，但不适用于像 M=100000 N=100000 这样的大输入。它显示类似 -nan 或任何负整数的内容。你的结果将是 1000000007 的模。我怎样才能得到这个大整数范围的准确答案？谢谢

#include<iostream>
#include<cmath>

using namespace std;

double factorial(int);

int main(){
  int m,n;
  double mod= 1000000007; 
    double p,q,result;
    cout << "\nPlease enter the dimensions of grid: "; 
    cin>>m>>n;
    if (m <0&&n<0)
    {
        cout << "Invalid dimensions!\n";
        return 1;
    }
    m++; n++; /*if n is the no of vertical/horizontal boxes,
                there will be n+1 vertical/horizontal lines in the grid */
    result=(factorial(m)/(2*factorial(m-2)))*(factorial(n)/(2*factorial(n-2)));
    cout<<"\nThe rectangles in the grid is:"<<fmod(result,mod);
    return 0;
}

double factorial(int x) {
    double temp;
    if(x <= 1) return 1;
    temp = x * factorial(x - 1);
    return temp;
}

Answer 1

你不能对双精度数进行 100000 阶乘，你会溢出（如你所见）。

在你的情况下，考虑一下你正在计算的内容的扩展

 m * (m-1) * (m-2) * (m-3) * ... * 2 * 1
-----------------------------------------
         2 * (m-2) * (m-3) * ... * 2 * 1

这一切都简化为 m * (m-1) / 2。因此，您根本不需要阶乘函数。

编辑：另一个post中的代码不正确。试试这个：

result = static_cast<double>(m) * (m-1) * n * (n-1) / 4;

Answer 2

与编程无关，但 factorial(m)/(2*factorial(m-2) 与 m * (m-1) / 2 相同，可能不会导致溢出。

Answer 3

#include<iostream>
#include<cmath>

using namespace std;

double factorial(int);

int main(){
  int m,n;
  double mod= 1000000007; 
    double p,q,result;
    cout << "\nPlease enter the dimensions of grid: "; 
    cin>>m>>n;
    if (m <0&&n<0)
    {
        cout << "Invalid dimensions!\n";
        return 1;
    }
    m++; n++; /*if n is the no of vertical/horizontal boxes,
                there will be n+1 vertical/horizontal lines in the grid */
   //This is where I had the typo. Forgot to divide by 2.
    result=((m*(m-1))/2)*((n*(n-1))/2);
    cout<<"\nThe rectangles in the grid is:"<<fmod(result,mod);
    return 0;
}

/*double factorial(int x) {
    double temp;
    if(x <= 1) return 1;
    temp = x * factorial(x - 1);
    return temp;
} */

这应该可以正常工作。您无需实现阶乘函数。你可以简化你的陈述，你会得到你的答案。

网格中的矩形总数？

total Number of rectangles in a grid?

c++

integer-overflow