Hay \(N\) ciudades. El tiempo que se tarda en viajar de la ciudad \(i\) a la ciudad \(j\) es \(T_{i, j}\).
Entre esos caminos que comienzan en la Ciudad \(1\), visite todas las demás ciudades exactamente una vez, y luego regrese a la Ciudad \(1\), ¿cuántos caminos toman el tiempo total de exactamente \(K\) para viajar?
Restricciones
- \(2≤N≤8\)
- Si \(i ≠ j\), \(1≤T_{i,j}≤10^8\).
- \(T_{i,i} = 0\)
- \(T_{i, j} = T_{j, i}\)
- \(1≤K≤10^9\)
- Todos los valores de la entrada son números enteros.
Entrada:
La primera línea de la entrada contiene \(N\) y \(K\). Siguen \(N\) líneas cada una con \(N\) enteros donde el elemento en la i-ésima fila y la columna \(j\) es \(T_{i,j}\).
Salida
Imprime la respuesta como un número entero.
Entrada de ejemplo 1:
4 330
0 1 10100
1 0 20 200
10 20 0 300
100 200 300 0
Salida de ejemplo: 1
2
Hay seis caminos que comienzan en la ciudad \(1\), visita todas las demás ciudades exactamente una vez y luego vuelve a la Ciudad \(1\):
1 → 2 → 3 → 4 → 1 1 → 2 → 4 → 3 → 1 1 → 3 → 2 → 4 → 1 1 → 3 → 4 → 2 → 1 1 → 4 → 2 → 3 → 1 1 → 4 → 3 → 2 → 1
El tiempo que se tarda en recorrer estos caminos es de \(421\), \(511\), \(330\), \(511\), \(330\) y \(421\), respectivamente, entre los cuales dos son exactamente \(330\).
Entrada de ejemplo 2:
5 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
Salida de ejemplo 2:
24
En cualquier orden en que visitemos las ciudades, tomará el tiempo total de \(5\) viajar.
Comments