NxM網格上的平行四邊形的數量

Question

當給定網格大小N×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個可能的平行四邊形。

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

P.S.我聽說我應該預處理最大公約數並將其保存在一個數組中，這會將運行時間減少到O（n * m），但我不確定如何在不使用cmmdc的情況下執行此操作（最大公約數）功能。

Answer 1

確保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; 
     } 
    } 
} 

不確定它是否有幫助。

Answer 2

代碼中的第一條評論指出「保持簡單」，所以，鑑於此，爲什麼不嘗試用數學方法解決問題並打印結果。

如果選擇從網格的長度爲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操作符）。

該計算所需的操作次數少於迭代矩陣。