Число параллелограммов на сетке NxM

Question

Я должен решить проблему, когда задан размер сетки 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); 
} 

Пример: 2х2 сетки есть 22 возможных параллелограммов.

Мой алгоритм работает, и это правильно, но мне нужно сделать это немного быстрее. Я хочу знать, как это возможно.

P.S. Я слышал, что я должен предварительно обработать наибольший общий делитель и сохранить его в массиве, который сократит время выполнения до O (n * m), но я не уверен, как это сделать без использования cmmdc (наибольший общий делитель).

Answer 1

Убедитесь, что N не меньше, чем М:

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, вероятно, будет возможно, вы можете инициализировать массив, используя вид алгоритма решета: Создание 2d массив, индексированный по a и b, поместите «2» в каждое положение, где a и b кратно 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; 
     } 
    } 
} 

Не уверен, что это помогает.

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.

Теперь, когда у вас есть решение для двух линий, вам просто нужно умножить его на число combinations порядка 2 м, что M!/(2*(M-2)!).

Таким образом, вся формула будет: 1/12*N*(2*N^2-3*N+1)*M!/(M-2)!, где ! знак обозначает factorial, а ^ обозначает оператор питания (обратите внимание, что тот же знак не оператор питания в C++, но оператор побитового XOR).

Этот расчет требует меньше операций, выполняющих итерацию через матрицу.