1

当给定网格大小 N x M 时，我必须解决一个问题，我必须找到“可以放入其中”的平行四边形的数量，这样它们的每个坐标都是整数。

这是我的代码：

/*
      ~Keep It Simple!~
*/

#include<fstream>

#define MaxN 2005

int N,M;
long long Paras[MaxN][MaxN]; // Number of parallelograms of Height i and Width j
long long Rects; // Final Number of Parallelograms

int cmmdc(int a,int b)
{
while(b)
{
    int aux = b;
    b = a -(( a/b ) * b);
    a = aux;
}

return a;
}

int main()
{
freopen("paralelograme.in","r",stdin);
freopen("paralelograme.out","w",stdout);

scanf("%d%d",&N,&M);

for(int i=2; i<=N+1; i++)
    for(int j=2; j<=M+1; j++)
    {
        if(!Paras[i][j])
          Paras[i][j] = Paras[j][i] = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2; // number of parallelograms with all edges on the grid + number of parallelograms with only 2 edges on the grid.
        Rects += 1LL*(M-j+2)*(N-i+2) * Paras[j][i]; // each parallelogram can be moved in (M-j+2)(N-i+2) places.
    }

printf("%lld", Rects);
}

示例：对于 2x2 网格，我们有 22 个可能的平行四边形。

我的算法有效并且是正确的，但我需要让它更快一点。我想知道这怎么可能。

PS我听说我应该预处理最大公约数并将其保存在一个数组中，这会将运行时间减少到O（n * m），但我不知道如何在不使用cmmdc的情况下做到这一点（最大公约数）函数。

4

2 回答 2

0

您的代码中的第一条注释声明“保持简单”，因此，鉴于此，为什么不尝试以数学方式解决问题并打印结果。

如果您从网格中选择两条长度为 N 的线，您将通过以下方式找到平行四边形的数量：

  • 在两条线上选择彼此相邻的两个点：有一些(N-1)^2 方法可以做到这一点，因为您可以将这两个点N-1 定位在每条线上的位置上。
  • 在两条线上选择两个点，它们之间有一个空格：有(N-2)^2办法做到这一点。
  • 选择两个点，它们之间有两个、三个和最多N-2空格。
  • 结果组合数为(N-1)^2+(N-2)^2+(N-3)^2+...+1。
  • 通过求解总和，我们得到公式：1/6*N*(2*N^2-3*N+1)。检查WolframAlpha进行验证。

现在您已经有了两条线的解决方案，您只需将它乘以M 的 2 阶组合数，即M!/(2*(M-2)!).

因此，整个公式将是：1/12*N*(2*N^2-3*N+1)*M!/(M-2)!，其中!标记表示阶乘，而^表示幂运算符（请注意，相同的符号不是 C++ 中的幂运算符，而是位运算XOR符）。

这种计算需要更少的操作，而不是遍历矩阵。

于 2014-01-27T21:42:30.727 回答
0

确保 N 不小于 M：

if( N < M ){ swap( N, M ); }

利用循环中的对称性，您只需将 j 从 2 运行到 i：

for(int j=2; j<=min( i, M+1); j++)

你不需要额外的数组Paras，放下它。而是使用临时变量。

long long temparas = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2;
long long t1 = temparas * (M-j+2)*(N-i+2);
Rects += t1;
// check if the inverse case i <-> j must be considered
if( i != j && i <= M+1 ) // j <= N+1 is always true because of j <= i <= N+1
    Rects += t1;

替换这一行：b = a -(( a/b ) * b);使用余数运算符：

b = a % b;

缓存 cmmdc 结果可能是可能的，您可以使用某种筛子算法初始化数组：创建一个由 a 和 b 索引的二维数组，在 a 和 b 是 2 的倍数的每个位置放置“2”，然后放置一个“ 3" 在每个位置 a 和 b 是 3 的倍数，依此类推，大致如下：

int gcd_cache[N][N];

void init_cache(){
    for (int u = 1; u < N; ++u){
        for (int i = u; i < N; i+=u ) for (int k = u; k < N ; k+=u ){
            gcd_cache[i][k] = u;
        }
    }
}

不确定它是否有很大帮助。

于 2014-01-27T21:16:43.270 回答