c++ - geeks - ¿Cómo acelerar la generación de series?

fibonacci series algorithm

Question

El problema requiere generar el elemento n-th de una secuencia que es similar a la secuencia de Fibonacci. Sin embargo, es un poco complicado porque n es muy grande (1 <= n <= 10 ^ 9). La respuesta entonces módulo 1000000007. La secuencia se define de la siguiente manera:

Usando la función de generación, obtengo la siguiente fórmula:

Si utilizo el enfoque de secuencia, la respuesta puede ser módulo, pero se ejecuta extremadamente lento. De hecho, tengo time limit exceed muchas veces. También intenté usar una tabla para generar previamente algunos valores iniciales (caché), pero no fue lo suficientemente rápido. Además, el número máximo de elementos que puedo almacenar en una array/vector (C ++) es demasiado pequeño en comparación con 10 ^ 9, así que supongo que este enfoque tampoco funciona.
Si utilizo la fórmula directa, se ejecuta extremadamente rápido pero solo para n que es pequeño. Para n grande, se truncará el doble, y además no podré modificar mi respuesta con ese número porque el módulo solo funciona con números enteros.
Me quedé sin ideas y creo que debe haber un buen truco para solucionar este problema, desafortunadamente no puedo pensar en uno. Cualquier idea sería muy apreciada.

Aquí está mi enfoque inicial:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <set>
#include <stack>
#include <sstream>
#include <cstdio>
#include <map>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

ull count_fair_coins_by_generating_function(ull n) {
    n--;
    return 
        (sqrt(3.0) + 1)/((sqrt(3.0) - 1) * 2 * sqrt(3.0)) * pow(2 / (sqrt(3.0) - 1), n * 1.0) 
        +
        (1 - sqrt(3.0))/((sqrt(3.0) + 1) * 2 * sqrt(3.0)) * pow(-2 / (sqrt(3.0) + 1), n * 1.0);
}

ull count_fair_coins(ull n) {
    if (n == 1) {
        return 1;
    }
    else if (n == 2) {
        return 3;
    }
    else {
        ull a1 = 1;
        ull a2 = 3;
        ull result;
        for (ull i = 3; i <= n; ++i) {
            result = (2*a2 + 2*a1) % 1000000007;
            a1 = a2;
            a2 = result;
        }

        return result;
    }
}

void inout_my_fair_coins() {
    int test_cases;
    cin >> test_cases;

    map<ull, ull> cache;
    ull n;
    while (test_cases--) {
        cin >> n;
        cout << count_fair_coins_by_generating_function(n) << endl;
        cout << count_fair_coins(n) << endl;
    }
}

int main() {
    inout_my_fair_coins();
    return 0;
} 

Actualización Desde que tskuzzy el tskuzzy mi solución basada en la idea tskuzzy para aquellos que estén interesados. Una vez más, gracias tskuzzy . Puede ver la declaración del problema original aquí: http://www.codechef.com/problems/CSUMD
Primero, debes calcular la probabilidad de esas 1 coin y 2 coin , luego obtener algunos valores iniciales para obtener la secuencia. La solución completa está aquí:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <set>
#include <stack>
#include <sstream>
#include <cstdio>
#include <map>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

const ull special_prime = 1000000007;

/*
    Using generating function for the recurrence:
           | 1                     if n = 1
    a_n =  | 3                     if n = 2
           | 2a_{n-1} + 2a_{n-2}     if n > 2

    This method is probably the fastest one but it won''t work 
    because when n is large, double just can''t afford it. Plus,
    using this formula, we can''t apply mod for floating point number.
    1 <= n <= 21
*/
ull count_fair_coins_by_generating_function(ull n) {
    n--;
    return 
        (sqrt(3.0) + 1)/((sqrt(3.0) - 1) * 2 * sqrt(3.0)) * pow(2 / (sqrt(3.0) - 1), n * 1.0) 
        +
        (1 - sqrt(3.0))/((sqrt(3.0) + 1) * 2 * sqrt(3.0)) * pow(-2 / (sqrt(3.0) + 1), n * 1.0);
}

/*
    Naive approach, it works but very slow. 
    Useful for testing.
*/
ull count_fair_coins(ull n) {
    if (n == 1) {
        return 1;
    }
    else if (n == 2) {
        return 3;
    }
    else {
        ull a1 = 1;
        ull a2 = 3;
        ull result;
        for (ull i = 3; i <= n; ++i) {
            result = (2*a2 + 2*a1) % 1000000007;
            a1 = a2;
            a2 = result;
        }

        return result;
    }
}

struct matrix_2_by_2 {
    ull m[2][2];
    ull a[2][2];
    ull b[2][2];

    explicit matrix_2_by_2(ull a00, ull a01, ull a10, ull a11) {
        m[0][0] = a00;
        m[0][1] = a01;
        m[1][0] = a10;
        m[1][1] = a11;
    }

    matrix_2_by_2 operator *(const matrix_2_by_2& rhs) const {
        matrix_2_by_2 result(0, 0, 0, 0);
        result.m[0][0] = (m[0][0] * rhs.m[0][0]) + (m[0][1] * rhs.m[1][0]);
        result.m[0][1] = (m[0][0] * rhs.m[0][1]) + (m[0][1] * rhs.m[1][1]);
        result.m[1][0] = (m[1][0] * rhs.m[0][0]) + (m[1][1] * rhs.m[1][0]);
        result.m[1][1] = (m[1][0] * rhs.m[0][1]) + (m[1][1] * rhs.m[1][1]);
        return result;
    }

    void square() {
        a[0][0] = b[0][0] = m[0][0];
        a[0][1] = b[0][1] = m[0][1];
        a[1][0] = b[1][0] = m[1][0];
        a[1][1] = b[1][1] = m[1][1];

        m[0][0] = (a[0][0] * b[0][0]) + (a[0][1] * b[1][0]);
        m[0][1] = (a[0][0] * b[0][1]) + (a[0][1] * b[1][1]);
        m[1][0] = (a[1][0] * b[0][0]) + (a[1][1] * b[1][0]);
        m[1][1] = (a[1][0] * b[0][1]) + (a[1][1] * b[1][1]);
    }

    void mod(ull n) {
        m[0][0] %= n;
        m[0][1] %= n;
        m[1][0] %= n;
        m[1][1] %= n;
    }

    /*
        exponentiation by squaring algorithm
                | 1                    if n = 0 
                | (1/x)^n              if n < 0 
        x^n =   | x.x^({(n-1)/2})^2    if n is odd
                | (x^{n/2})^2          if n is even

        The following algorithm calculate a^p % m
        int modulo(int a, int p, int m){
            long long x = 1;
            long long y = a; 

            while (p > 0) {
                if (p % 2 == 1){
                    x = (x * y) % m;
                }

                // squaring the base
                y = (y * y) % m; 
                p /= 2;
            }

            return x % c;
        }

        To apply for matrix, we need an identity which is
        equivalent to 1, then perform multiplication for matrix 
        in similar manner. Thus the algorithm is defined 
        as follows:
    */
    void operator ^=(ull p) {
        matrix_2_by_2 identity(1, 0, 0, 1);

        while (p > 0) {
            if (p % 2) {
                identity = operator*(identity);
                identity.mod(special_prime);
            }

            this->square();
            this->mod(special_prime);
            p /= 2;
        }

        m[0][0] = identity.m[0][0];
        m[0][1] = identity.m[0][1];
        m[1][0] = identity.m[1][0];
        m[1][1] = identity.m[1][1];
    }

    friend
    ostream& operator <<(ostream& out, const matrix_2_by_2& rhs) {
        out << rhs.m[0][0] << '' '' << rhs.m[0][1] << ''/n'';
        out << rhs.m[1][0] << '' '' << rhs.m[1][1] << ''/n'';
        return out;
    }
};

/*
    |a_{n+2}| = |2 2|^n  x |3| 
    |a_{n+1}|   |1 0|      |1|
*/
ull count_fair_coins_by_matrix(ull n) {
    if (n == 1) {
        return 1;
    } else {
        matrix_2_by_2 m(2, 2, 1, 0);
        m ^= (n - 1);
        return (m.m[1][0] * 3 + m.m[1][1]) % 1000000007;
    }
}

void inout_my_fair_coins() {
    int test_cases;
    scanf("%d", &test_cases);

    ull n;
    while (test_cases--) {
        scanf("%llu", &n);
        printf("%d/n", count_fair_coins_by_matrix(n));
    }
}

int main() {
    inout_my_fair_coins();
    return 0;
}  

Answer 1

Puede escribir los términos de la secuencia en términos de exponenciales matriciales:

el cual puede ser rápidamente evaluado usando exponenciación por cuadratura . Esto conduce a una solución O(log n) que debería resolver el problema bien dentro de las restricciones de tiempo.

Solo para futuras referencias, si se requiere que hagas una multiplicación con números grandes (no aplicable en esta situación, ya que la respuesta se toma en módulo 1000000007), debes buscar el algoritmo de Karatsuba . Esto te da la multiplicación de tiempo sub-cuadrática.

Answer 2

Solo piense aquí, pero eche un vistazo al dispositivo de Duff para la función count_fair_coins ya que esto desenrollará automáticamente el bucle para acelerar esa función.

Precomputar los sqrt en la función de generación parece ser la forma más fácil de acelerar. Lo que se reduciría a una sola llamada de potencia y multiplicación de constantes. Además de precalcular el sqrt, otra forma de acelerarlo es eliminar las divisiones y utilizar la multiplicación inversa, aunque una optimización muy leve puede ayudar a acelerar cuando n es muy grande.