Количество параллелограммов на сетке NxM
Я должен решить проблему, когда, учитывая размер сетки 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 возможных параллелограмма.
Мой алгоритм работает, и он правильный, но мне нужно сделать его немного быстрее. Я хочу знать, как это возможно.
Постскриптум Я слышал, что я должен предварительно обработать наибольший общий делитель и сохранить его в массиве, который сократит время выполнения до O (n * m), но я не уверен, как это сделать без использования cmmdc ( наибольший общий делитель) функция.
Решение
Убедитесь, что 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;
}
}
}
Не уверен, что это сильно поможет.
Другие решения
Первый комментарий в вашем коде гласит: «будь проще», поэтому, в свете этого, почему бы не попытаться решить проблему математически и распечатать результат.
Если вы выберете две линии длины 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), Проверьте Вольфрам Альфа проверять.
Теперь, когда у вас есть решение для двух строк, вам просто нужно умножить его на число комбинации порядка 2 М, который является M!/(2*(M-2)!),
Таким образом, вся формула будет: 1/12*N*(2*N^2-3*N+1)*M!/(M-2)!, где ! знак обозначает факториал, и ^ обозначает оператор степени (обратите внимание, что тот же знак не является оператором степени в C ++, но побитовый XOR оператор).
Этот расчет требует меньше операций, чем итерация по матрице.