как рассчитать 2^n по модулю 1000000007, n = 10^9

каков самый быстрый способ вычислить это, я видел, как некоторые люди используют матрицы, и когда я искал в Интернете, они говорили о собственных значениях и собственных векторах (не знаю об этом)... был вопрос, который сводился к рекурсивному уравнение f(n) = (2*f(n-1)) + 2 и f(1) = 1, n может быть до 10 ^ 9.... я уже пытался использовать DP, сохраняя до 1000000 значений и используя общий метод быстрого возведения в степень, все время истекло, я обычно слаб в этих вопросах по модулю, которые требуют вычисления больших значений


matrix math exponentiation eigenvalue eigenvector
person manu4rhyme    schedule 24.05.2014    source источник
comment
Какой язык/инструмент? Обычно такие вычисления выполняет функция PowMod или ModPow. См. en.wikipedia.org/wiki/Modular_exponentiation.   -  person hatchet - done with SOverflow    schedule 24.05.2014
comment
Самый быстрый способ — карандаш и бумага: 140625001   -  person ypercubeᵀᴹ    schedule 24.05.2014
comment
Это повторяющаяся тема, просто найдите этот специальный номер, stackoverflow.com/search?tab=relevance&q=1000000007. . Например, в stackoverflow.com/questions/9220416/need -help-in-mod-1000000007 или дубликат stackoverflow.com/questions/11289495/   -  person Lutz Lehmann    schedule 24.05.2014

Ответы (3)


arrow_upward
2
arrow_downward 

f(n) = (2*f(n-1)) + 2 with f(1)=1

эквивалентно

(f(n)+2) = 2 * (f(n-1)+2)
         = ...
         = 2^(n-1) * (f(1)+2) = 3 * 2^(n-1)

так что наконец

f(n) = 3 * 2^(n-1) - 2

где затем можно применить быстрые модульные методы питания.

person Lutz Lehmann    schedule 24.05.2014
comment
Для немецкоязычных, интересующихся, я смутно припоминаю тему, затронутую в учебнике Algorithmische Zahlentheorie Отто Форстера. - person Codor; 24.05.2014

arrow_upward
2
arrow_downward

Модульное возведение в степень методом квадрата и умножения:

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x
person user448810    schedule 24.05.2014
comment
это удивительное решение - person sahasrara62; 10.06.2019

arrow_upward
0
arrow_downward

Код C для вычисления 2^n

    const int mod = 1e9+7;

    //Here base is assumed to be 2
    int cal_pow(int x){
        int res;
        if (x == 0) res=1;
        else if (x == 1)    res=2;
        else {
            res = cal_pow(x/2);
            if (x % 2 == 0) 
                res = (res * res) % mod;
            else
                res = (((res*res) % mod) * 2) % mod;
        }
        return res;
    }
person ssp4all    schedule 10.06.2019
comment
Может быть, да, но он все еще требует некоторой модификации. правильно? - person ssp4all; 11.06.2019
comment
не проверял результат, но видя что он делает, вы должны удалить его на время - person sahasrara62; 11.06.2019
comment
Внесены необходимые изменения, и это не дает прямых результатов! - person ssp4all; 11.06.2019