Количество параллелограммов на сетке 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);
}

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

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

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

Answer 1

Убедитесь, что 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, поместите "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, чтобы проверить.

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

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

Этот расчет требует меньше операций, чем итерация по матрице.