Calcule la suma en Descomposición de array diagonal eliminando elementos en forma de L

Dados dos enteros N que representan la dimensión de una array cuadrada y un entero A con el que se inicializa la array. Dado otro mod entero . Calcular la suma requerida siguiendo los pasos dados:

• Seleccione el producto de todos los elementos en forma de L comenzando desde el elemento superior derecho, agréguelo a la suma y elimínelos todos de la array.
• Multiplique el término eliminado en el paso anterior con todos los demás elementos que quedan en la array.
• Como la suma puede ser muy grande, imprímala módulo mod .

Ejemplos:

Entrada: N = 3, A = 3, mod = 1000000007
Salida: 953271922
Explicación:   1.2157665459E19 % 1000000007 = 953271922

Calcule la suma en Descomposición de array diagonal eliminando elementos en forma de L

Entrada: N = 2, A = 1, mod = 2
Salida: 0

Planteamiento: Es obvio que no se pueden crear arrays para grandes dimensiones. Además, se puede observar que se está formando una serie con potencias impares en cada término donde cada término tiene base como una potencia más del término anterior y exponente como número de elementos que se quitan cada vez. Siga los pasos dados para resolver el problema: 

• Cree una función rápida de exponenciación modular Mod_Power utilizando el concepto de exponenciación binaria .
• Pase A , 2*i-1 y mod a Mod_Power donde 2*i-1 son las potencias impares a partir de 1 y almacene el resultado en (por ejemplo, en un término variable ).
• Calcule la suma sumando todos los valores del término .
• Actualice la base del nuevo término A como producto del término y A .

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

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// Function to calculate the power
ll Mod_Power(ll x, ll y, ll m)
{
    ll res = 1;
 
    while (y) {
        if (y & 1)
            res = (res * x) % m;
        x = ((x * x) % m + m) % m;
        y = y >> 1; // y=y/2
    }
    return (res % m + m) % m;
}
 
// Function to get the required sum
ll req_Sum(ll n, ll a, ll m)
{
    ll sum = 0, term;
 
    for (int i = 1; i <= n; i++) {
        term = Mod_Power(a, 2 * i - 1, m);
        sum += (term % m);
        a = ((a * term) % m + m) % m;
    }
    return (sum % m + m) % m;
}
 
// driver's code
int main()
{
    int N = 3;
    int A = 3;
    int mod = 1000000007;
    cout << req_Sum(N, A, mod);
 
    return 0;
}
// this code is contributed by prophet1999

import java.util.*;
 
public class GFG {
    // Function to calculate the power
    static long Mod_Power(long x, long y, long mod)
    {
        long res = 1;
        while (y > 0) {
            if (y % 2 == 1)
                res = (res * x) % mod;
            x = ((x * x) % mod + mod) % mod;
            y = y >> 1;
        }
        return (res % mod + mod) % mod;
    }
 
    // Function to get the required sum
    static long req_Sum(long N, long A, long mod)
    {
        long sum = 0, term;
        for (int i = 1; i <= N; i++) {
            term = Mod_Power(A, 2 * i - 1, mod);
            sum += (term % mod);
            A = ((A * term) % mod + mod) % mod;
        }
        return (sum % mod + mod) % mod;
    }
 
    // Driver's code
    public static void main(String[] args)
    {
 
        // Java code to implement the approach
        int N = 3;
        int A = 3;
        int mod = 1000000007;
        System.out.print(req_Sum(N, A, mod));
    }
}
// this code is contributed by prophet1999

# Python code to implement the approach
 
# Function to calculate the power
def Mod_Power(x, y, m):
     
    res = 1
 
    while (y):
        if (y & 1):
            res = (res * x) % m
        x = ((x * x) % m + m) % m
        y = y >> 1 # y=y/2
     
    return (res % m + m) % m
 
# Function to get the required sum
def req_Sum(n, a, m):
 
    sum = 0
    term = 0
 
    for i in range(1, n + 1):
        term = Mod_Power(a, 2 * i - 1, m)
        sum += (term % m)
        a = ((a * term) % m + m) % m
     
    return (sum % m + m) % m
 
# driver's code
 
N = 3
A = 3
mod = 1000000007
print(req_Sum(N, A, mod))
 
# this code is contributed by Samim Hossain Mondal.

// C# code to implement the approach
using System;
class GFG
{
 
  // Function to calculate the power
  static long Mod_Power(long x, long y, long m)
  {
    long res = 1;
 
    while (y != 0) {
      if (y % 2 == 1)
        res = (res * x) % m;
      x = ((x * x) % m + m) % m;
      y = y >> 1; // y=y/2
    }
    return (res % m + m) % m;
  }
 
  // Function to get the required sum
  static long req_Sum(long n, long a, long m)
  {
    long sum = 0, term;
 
    for (int i = 1; i <= n; i++) {
      term = Mod_Power(a, 2 * i - 1, m);
      sum += (term % m);
      a = ((a * term) % m + m) % m;
    }
    return (sum % m + m) % m;
  }
 
  // driver's code
  public static int Main()
  {
    int N = 3;
    int A = 3;
    int mod = 1000000007;
    Console.Write(req_Sum(N, A, mod));
    return 0;
  }
}
 
// This code is contributed by Taranpreet

<script>
// Javascript code to implement the approach
 
// Function to calculate the power
function Mod_Power(x, y, m)
{
    let res = 1;
 
    while (y) {
        if (y & 1)
            res = (res * x) % m;
        x = ((x * x) % m + m) % m;
        y = y >> 1; // y=y/2
    }
    return (res % m + m) % m;
}
 
// Function to get the required sum
function req_Sum(n, a, m)
{
    let sum = 0, term;
 
    for (let i = 1; i <= n; i++) {
        term = Mod_Power(a, 2 * i - 1, m);
        sum += (term % m);
        a = ((a * term) % m + m) % m;
    }
    return (sum % m + m) % m;
}
 
// driver's code
 
let N = 3;
let A = 3;
let mod = 1000000007;
document.write(req_Sum(N, A, mod));
 
// this code is contributed by Samim Hossain Mondal.
</script>

953271922

Complejidad de Tiempo: O(N * log (N ² ))
Espacio Auxiliar: O(1)