Observación 1: La paridad del número de divisores de un número depende de si es un cuadrado perfecto o no. Si es un cuadrado perfecto, entonces tiene un número impar de divisores; de lo contrario, tiene un número par de divisores.

Subtarea 1

En esta subtarea se cumple que ~a_1 = a_2 = \dots = a_n~. Cuando ~n=1~ existe una sola permutación y esta cumple la condición de ~k-~perfección. Cuando ~n>1~ notar que como todos los elementos de la secuencia son iguales solo hace falta chequear que los dos primeros elementos cumplan la condición de ~k-~perfección, si cumplen la condición entonces la respuesta es ~n!~ porque cualquier permutación de los índices que se pueda hacer es una permutación válida, de lo contrario la respuesta sería ~0~.

Complejidad: ~O(n)~

Subtarea 2

En esta subtarea se cumple ~1 \le n \le 5~. Para esta subtarea era suficiente iterar por todas las permutaciones de los índices y verificar si los consecutivos cumplían la condición de ~k-~perfección.

Complejidad: ~O(n!)~

vector<ll> p(n); iota(p.begin(), p.end(), 0);

int res = 0;
do {
  bool ok = true;
  for (int i = 0; i < n - 1; i++) {
    if (!kPerfect(a[p[i]] * a[p[i + 1]], k)) {
      ok = false; break;
    }
  }

  res = (res + ok) % MOD;
} while (next_permutation(p.begin(), p.end()));

Subtarea 3

En esta subtarea se cumple que ~k=1~. Cuando ~n=1~ existe una sola permutación y esta cumple la condición de ~1-~perfección. Cuando todos los elementos son iguales sería resolver la subtarea 1. De lo contrario, si hay al menos dos elementos distintos, podemos factorizar en primos cada uno de los números y quedarnos solo con los primos que tengan una potencia impar para cada una de las posiciones. Por ejemplo, si ~a = [3, 12, 30]~, ~3 = 3^1, 12 = 3^1 * 2^2, 30 = 2 * 3 * 5~ y el nuevo arreglo ~a' = [3, 3, 30]~. Si la cantidad de elementos distintos que hay en este arreglo es distinto de ~1~ entonces la solución es ~0~, de lo contrario es ~n!~.

Complejidad: ~O(n)~

Subtarea 4

En esta subtarea se cumple que ~1 \le n \le 16~. Cuando ~k=1~ procedemos a resolver la subtarea 3. Veamos para ~k=0~. La idea para resolver esta subtarea es utilizar dp con máscara de bits.

Sea ~dp(mask, i)~ la cantidad de formas de reorganizar el subconjunto al que representa ~mask~ siendo el número de la posición ~i~ el último número de la secuencia. Entonces la respuesta es ~\sum_{i=0}^{n-1} dp(2^{n}-1, i)~.

Los casos bases son cuando ~mask~ representa solamente a un número, ~dp(mask, p) = 1~ donde ~p~ es el la posición del número representado por ~mask~, es decir, para todo ~i~ se cumple que ~dp(2^i,i) = 1~. A partir de estos casos bases es fácil notar que ~dp(mask, i) = dp(mask - 2^i, j)~ para todo ~j~ que cumpla ~a_i * a_j~ sea ~k-~perfecto.

Complejidad: ~O(2^n * n^2)~

Subtarea 5

Si ~k=1~ procedemos a resolver la subtarea 3. Veamos la solución para ~k=0~, la primera idea es "comprimir" el arreglo en otro arreglo donde todos los elementos no "semejantes" queden en una misma posición.

Si ~a_i * a_{i+1}~ tiene un número par de divisores, entonces ~a_i *a_{i+1}~ no es un cuadrado perfecto, por lo que el problema se reduce a contar la cantidad de formas de reorganizar el arreglo para que ~a_i * a_{i+1}~ (~1 \le i < n~) no sea un cuadrado perfecto. Tenga en cuenta que si ~x * y~ y ~y * z~ son cuadrados perfectos, entonces ~x * z~ también es un cuadrado perfecto (transitivo). También tenemos que ~x * x~ es un cuadrado perfecto para cada ~x~ (reflexivo), y si ~x * y~ es un cuadrado perfecto, entonces ~y * x~ también es un cuadrado perfecto (simétrico). Podemos concluir que la relación de cuadrado perfecto es una relación de equivalencia (en adelante referida como ~r~). Se sabe que existe una partición única ~a/e~. Dada la partición ~p = a/r~, el problema se reduce a reorganizar ~a~ de tal manera que dos elementos consecutivos no estén en la misma clase de equivalencia de la partición ~p~. El nuevo problema se puede resolver utilizando programación dinámica en ~O(n^3)~.

Considere un nuevo arreglo donde los elementos en la misma partición tienen el mismo valor. Agrupamos todos los valores distintos en el arreglo.

Entonces el problema se reduce a contar la cantidad de formas de reorganizar el nuevo arreglo de tal forma que dos elementos consecutivos sean diferentes. Este nuevo problema puede ser resuelto utilizando programación dinámica:

Sea ~dp_{i, j}~ la cantidad de arreglos distintos que se pueden obtener utilizando los elementos de los primeros ~i~ grupos de manera que haya exactamente ~j~ pares de posiciones consecutivas con el mismo valor. La respuesta se puede encontrar en ~dp_{valores\_distintos, 0}~.

Ahora supongamos que la suma de las frecuencias de los primeros ~i~ valores es ~X~. Esto significa que los arreglos que podemos construir utilizando los elementos de estos ~i~ grupos tienen tamaño ~X~, por lo que podemos insertar los elementos del grupo ~i + 1~ en ~X + 1~ espacios: antes del primer número, después del último y entre cualquier par de elementos consecutivos. Podemos fijar el número ~k~ de espacios donde queremos insertar al menos un número del grupo ~i + 1~, pero también necesitamos fijar el número ~l~ de estos ~k~ espacios que estarán entre elementos que previamente tenían el mismo valor. El estado ~dp_{i,j}~ actualizará el estado ~dp_{i + 1,j - l + frecuencia(i + 1 - k)}~.

La cantidad de formas de elegir ~k~ espacios de manera que exactamente ~l~ estén entre elementos consecutivos que tienen el mismo valor se puede calcular fácilmente utilizando fórmulas de combinaciones. Nos queda encontrar la cantidad de formas de insertar ~frecuencia(i + 1)~ elementos en ~k~ espacios. Este también es un problema clásico con una respuesta simple: ~frecuencia(i + 1) - 1 \choose k - 1~.

Complejidad: ~O(n^3)~