Hola,
estoy resolviendo este problema.
Mi solución es la siguiente:
Resumen
#include<bits/stdc++.h>
using namespace std;
#define tint long long
#define forsn(i, s, n) for(tint i=s;i<int(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) (v.begin(), v.end())
tint numeroCombinatorio(tint n, tint k){
if(k==0 || k==n) return 1;
return numeroCombinatorio(n-1, k)+numeroCombinatorio(n-1, k-1);
}
int main(){
tint n; cin >> n;
forn(i, n){
if(i==0) cout << 0 << endl;
else{
cout << (numeroCombinatorio((i+1)*(i+1), 2))-(4*i*(i-1)) << endl;
}
}
}
Tengo una funcion que calcula \binom{n}{k}.
Luego, para calcular la cantidad de formas de colocar dos caballos en un tablero de n*n de tal forma que no se ataquen entre ellos, hago \binom{n*n}{2}-4*(n-1)*(n-2), donde \binom{n*n}{2} es la forma de colocar dos caballos en un tablero y 4*(n-1)*(n-2) es la forma de colocar dos caballos en un tablero con la condición de que estos se ataquen, ya que un par de caballos atacados determina un rectángulo de 2*3 0 3*2, y hay 2*(n-1)*(n-2) rectángulos en en tablero inicial que son de este tipo. A esto se lo multiplica por dos ya que hay dos formas de poner los caballos en cada rectángulo.
Hay un caso de prueba en el cual n=10000, y me tirá “execution timed out”.
Alguien sabe como puedo hacer mi solución más eficiente?