Recuento de permutaciones tal que el GCD de todos los elementos multiplicados por la posición no es 1

Dada una array de enteros que tiene N elementos que van de 1 a N y cada elemento aparece exactamente una vez. La tarea es encontrar el número de posibles permutaciones tales que el MCD de todos los elementos multiplicado por su posición sea mayor que 1.

Nota: Como la respuesta puede ser muy grande, devuelva la respuesta módulo 10 ⁹ + 7

Ejemplos:

Entrada: N = 2, arr[] = {1, 2}
Salida: 1
Explicación: La única permutación válida será [2, 1] porque MCD(1*2, 2*1) = 2.

Entrada: N = 4, arr[] = {4, 1, 3, 2}
Salida: 4
Explicación:
Las permutaciones válidas serán 
[4, 3, 2, 1] con MCD(1*4, 2*3, 3 *2, 4*1) = 2.
[2, 3, 4, 1] con MCD(1*2, 2*3, 3*4, 4*1) = 2.
[2, 1, 4, 3] con MCD(1*2, 2*1, 3*4, 4*3) = 2.
[4, 1, 2, 3] con MCD(1*4, 2*1, 3*2, 4*3) = 2

Planteamiento: La idea para resolver el problema es la siguiente:

Trate de hacer que el producto de la posición y el número sea par, entonces en esa situación GCD será al menos 2.
Entonces, si N es impar, habrá 1 elemento impar más que las posibles posiciones pares. Entonces no es posible ninguna permutación.
De lo contrario 

• ¡los N/2 elementos pares se pueden organizar en (N/2)! maneras.
• ¡Para cada uno de estos arreglos se pueden ordenar N/2 elementos impares en (N/2)! maneras.

Así que el número total de formas posibles es ((N/2)!) ² .

Siga los pasos a continuación para resolver este problema:

• Si N es impar, devuelve 0.
• Inicialice una variable para almacenar la respuesta (digamos ans = 1 ).
• Travesía de i = 1 a N/2 .
  • Hacer ans igual a ans * i * i % MOD .
  • Encuentre la moda de ans .
• Regresar respuesta .

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1000000007;
 
// Function to find
// the number of valid permutations
int ValidPerm(int n, int a[])
{
    // If n is odd
    if (n & 1) {
        return 0;
    }
    long long ans = 1;
 
    // Counting number of permutations
    for (int i = 1; i <= n / 2; ++i) {
        ans *= i * i % MOD;
        ans %= MOD;
    }
 
    // Return the number of
    // possible permutations
    return ans;
}
 
// Driver code
int main()
{
    int N = 4;
    int arr[N] = { 1, 3, 2, 4 };
 
    // Function call
    cout << ValidPerm(N, arr);
    return 0;
}

// Java code to implement the above approach
import java.util.*;
public class GFG {
 
    static int MOD = 1000000007;
 
    // Function to find
    // the number of valid permutations
    static int ValidPerm(int n, int a[])
    {
        // If n is odd
        if ((n & 1) == 1) {
            return 0;
        }
        long ans = 1;
 
        // Counting number of permutations
        for (int i = 1; i <= n / 2; ++i) {
            ans *= i * i % MOD;
            ans %= MOD;
        }
 
        // Return the number of
        // possible permutations
        return (int)ans;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int N = 4;
        int arr[] = { 1, 3, 2, 4 };
 
        // Function call
        System.out.println(ValidPerm(N, arr));
    }
}
// This code is contributed by Samim Hossain Mondal.

# Python code to implement the above approach
MOD = 1000000007
 
# Function to find
# the number of valid permutations
def ValidPerm(n, a):
   
    # If n is odd
    if (n & 1):
        return 0
     
    ans = 1
 
    # Counting number of permutations
    for i in range(1,(n // 2)+1):
        ans *= i * i % MOD
        ans %= MOD
 
    # Return the number of
    # possible permutations
    return ans
 
# Driver code
 
N = 4
arr = [1, 3, 2, 4]
 
# Function call
print(ValidPerm(N, arr));
 
# This code is contributed by shinjanpatra

// C# code to implement the above approach
using System;
public class GFG {
 
  static int MOD = 1000000007;
 
  // Function to find
  // the number of valid permutations
  static int ValidPerm(int n, int []a)
  {
    // If n is odd
    if ((n & 1) == 1) {
      return 0;
    }
    long ans = 1;
 
    // Counting number of permutations
    for (int i = 1; i <= n / 2; ++i) {
      ans *= i * i % MOD;
      ans %= MOD;
    }
 
    // Return the number of
    // possible permutations
    return (int)ans;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 4;
    int []arr = { 1, 3, 2, 4 };
 
    // Function call
    Console.WriteLine(ValidPerm(N, arr));
  }
}
 
// This code is contributed by jana_sayantan.

<script>
    // JavaScript code to implement the above approach
 
    const MOD = 1000000007;
 
    // Function to find
    // the number of valid permutations
    const ValidPerm = (n, a) => {
        // If n is odd
        if (n & 1) {
            return 0;
        }
        let ans = 1;
 
        // Counting number of permutations
        for (let i = 1; i <= n / 2; ++i) {
            ans *= i * i % MOD;
            ans %= MOD;
        }
 
        // Return the number of
        // possible permutations
        return ans;
    }
 
    // Driver code
 
    let N = 4;
    let arr = [1, 3, 2, 4];
 
    // Function call
    document.write(ValidPerm(N, arr));
 
// This code is contributed by rakeshsahni
 
</script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(1)