Может ли кто-нибудь уменьшить сложность моего кода. Задача E раунда Codeforces 113, раздел 2

Question

Ссылка на проблему: https://codeforces.com/problemset/problem/166/E

Постановка задачи:

* Вам дан тетраэдр. Обозначим его вершины буквами A, B, C и D соответственно.

В вершине D тетраэдра стоит муравей. Муравей довольно активен и не будет бездействовать. В каждый момент времени он делает шаг от одной вершины к другой по некоторому ребру тетраэдра. Муравей просто не может стоять на одном месте. Для решения проблемы много делать не нужно: ваша задача - подсчитать количество способов, которыми муравей может go из начальной вершины D к себе ровно за n шагов. Другими словами, вам предлагается узнать количество различных циклических c путей длиной n от вершины D до самой себя. Поскольку число может быть довольно большим, вы должны вывести его по модулю 1000000007 (10 ^ 9 + 7). *

Ввод: Первая строка содержит единственное целое число n (1 ≤ n ≤ 107) - требуемая длина цикла c пути.

Вывод: Вывести единственное целое число - необходимое количество путей по модулю 1000000007 (10e9 + 7).

Пример: вход n = 2, выход: 3 вход n = 4, выход: 21

Мой подход к проблеме: Я написал рекурсивный код, который принимает два входа n и представляет index, то я путешествую и исследую все возможные комбинации.

#include<iostream>
using namespace std;
#define mod 10000000
#define ll long long   
ll count_moves=0;
ll count(ll n, int present)
{   
    if(n==0 and present==0) count_moves+=1, count_moves%=mod;  //base_condition
    else if(n>1){   //Generating All possible Combinations 
        count(n-1,(present+1)%4);
        count(n-1,(present+2)%4);
        count(n-1,(present+3)%4);
    }
    else if(n==1 and present) count(n-1,0);
}

int main()
{
    ll n;  cin>>n;
    if(n==1) { 
         cout<<"0";  return;   
    } 
    count(n,0);
    cout<<count_moves%mod;
}

Но проблема в том, что я получаю ошибку ограничения времени, так как сложность времени моего кода очень высока. Пожалуйста, кто-нибудь может предложить мне, как я могу оптимизировать / запоминать мой код, чтобы уменьшить его сложность?

# ** Редактировать 1: ** Некоторые люди комментируют макросы и деление, но это не проблема. Диапазон n равен 10 ^ 7, а сложность моего кода экспоненциальна, поэтому я действительно сомневаюсь, как уменьшить его до линейного времени. i, e O (n).

Answer 1

Каждый раз, когда вы встраиваете рекурсию и превышаете временную сложность, вы должны понимать, что рекурсия, вероятно, является проблемой.

Лучшее решение - не использовать рекурсию.

Посмотрите на результат у вас:

3 6 21 60 183 546 1641 4920

⋮ ⋮

Хотя может быть сложно найти образец для первых пар терминов, но позже это станет легче.

Каждый член примерно в 3 раза больше, чем последний член, или, точнее,

Now you could just write a for loop for it:

for(int i = 0; i < n-1; i++)
{
    count_moves = count_moves * 3 + std::pow(-1, i) * 3;
}

or to get rid of pow():

for(int i = 0; i < n-1; i++)
{
    count_moves = count_moves * 3 + (i % 2 * 2 - 1) * -3;
}

Further more, you could even build that into a general term formula to get rid of the for loop: введите описание изображения здесь или в коде:

count_moves = (pow(3, n) + (n % 2 * 2 - 1) * -3) / 4;

Однако вы не можете избавиться от pow() на этот раз, иначе вам придется написать для этого al oop.

Answer 2

Я считаю, что одна из ваших проблем заключается в том, что вы пересчитываете вещи.

Возьмем, например, n = 4. count (3, x) вызывается 3 раза для x в [0,3].

Однако, если вы сделали std :: map вы можете сохранить значение для пар (n, настоящее) и вычислить каждое значение только один раз.

Это займет больше места. Когда вы закончите, карта будет иметь размер 4 * (n-1). Это все еще, вероятно, слишком велико для 10 ^ 9?

Еще одна вещь, которую вы можете сделать, - это многопоточность. Каждый вызов count может инициировать свой собственный поток. Вам нужно быть осторожным, чтобы быть потокобезопасным при изменении глобального счетчика и состояния std :: map, если вы решили его использовать.

Изменить: вычислить count (n, x) один раз для n в [1, n-1] x в [0,3], затем count [n, 0] = a * count (n-1,1) + b * count (n-1,2) + c* count (n-1,3).

Если вы можете выяснить шаблон для каких a, b, c даны n или, может быть, даже a, b, c для случая n-1 тогда вы сможете легко решить эту проблему.