NxM网格上的平行四边形的数量

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

这里是我的代码：

/* 
     ~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个可能的平行四边形。

我的算法的工作原理和它是正确的，但我需要使它更快一点。我想知道它怎么可能。

P.S.我听说我应该预处理最大公约数并将其保存在一个数组中，这会将运行时间减少到O（n * m），但我不确定如何在不使用cmmdc的情况下执行此操作（最大公约数）功能。

来源

2014-01-27 user3220503

嗨。我很确定你的计算机科学老师只是问你这个问题，让你找出这个问题有多难。接下来你可能会学到的是基于格问题的密码学（又名下一个大事，那个量子计算机还不能打破:-) –

这不是我的计算机科学老师问我的东西，我可能有十倍比我的计算机科学老师更多的知识。这只是我准备在我的国家算法olymics。 – user3220503

确保N是小于M不小于：

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

利用您的循环对称性，你只需要2运行J可我：

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”，然后在a和b为3的倍数的每个位置放置“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-27 21:16:43 pentadecagon

你的第一个2 ideeas似乎加快了一些事情，但产生了一半正确的来源。有了我首先发布的消息，我得到了所有测试中的所有核心答案（除了一个错过了时间限制之外）。随着你的来源寿我只有50％的测试正确，所有的时间限制。 – user3220503

我发现了原因并编辑了答案，对于这两种情况，t1是不一样的。但是使用这种解决方案，它仍然不会在时间限制内。 – user3220503

您的所有ideeas都使代码速度提高了3倍。感谢名单。 – user3220503

代码中的第一条评论指出“保持简单”，所以，鉴于此，为什么不尝试用数学方法解决问题并打印结果。

如果选择从网格的长度为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，这是M!/(2*(M-2)!)的2阶combinations数相乘。

因此，整个公式将是：1/12*N*(2*N^2-3*N+1)*M!/(M-2)!，其中!马克表示factorial和^表示功率操作者（请注意，相同的符号是不是在C++中的功率操作，但按位XOR操作符）。

该计算所需的操作次数少于迭代矩阵。

来源

2014-01-27 21:42:30

我确实在数学上解决了它，上面有2个公式，事情是，我需要它在0.4秒内在2000x2000网格上运行。 Keep it simple标签是我放入每个程序中的东西 – user3220503

NxM网格上的平行四边形的数量

回答

相关问题