c++ - 任何人都可以降低我的代码的复杂性。 Codeforces Round113 Div.2的问题E

Question

链接到问题:https://codeforces.com/problemset/problem/166/E
问题陈述:
*您被赋予四面体。让我们分别用字母A，B，C和D标记其顶点。
一只 Ant 站在四面体的顶点D中。 Ant 很活跃，他不会闲着。在每个时刻，他都沿着四面体的某个边缘从一个顶点向另一个顶点迈出一步。 Ant 不能站在一个地方。
您无需做太多的工作来解决问题:您的任务是计算 Ant 从n个顶点到n个顶点的步长为n步的数量。换句话说，要求您找出从顶点D到自身的长度为n的不同循环路径的数量。由于数字可能很大，因此您应该以1000000007(10 ^ 9 + 7)为模数进行打印。*
输入:
第一行包含唯一的整数n(1≤n≤107)-循环路径的所需长度。
输出:
打印唯一的整数-所需的模数为1000000007(10e9 + 7)的方式。
示例:输入n = 2，输出:3
输入n = 4，输出:21
我的问题解决方法:
我编写了一个递归代码，该代码接受两个输入n和当前索引，然后旅行并探索所有可能的组合。

#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，我的代码的复杂度是指数级的，所以我的实际疑问是如何将其减少到线性时间。即O(n)。

Answer 1

每当您构建递归并且超过时间复杂度时，您都必须了解递归可能是问题所在。
最好的解决方案是不使用递归。
查看结果:

3

6

21

60

183

546

1641

4920

⋮⋮
虽然可能很难找到前几个术语的模式，但以后会更容易。
每学期约比上学期大3倍，或更准确地说，

现在您可以为其编写一个for循环:

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

或摆脱 pow():

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

更进一步，您甚至可以将其内置到通用术语公式中以摆脱for循环:

或在代码中:

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

但是，您这次无法摆脱 pow()，否则您将不得不为此编写一个循环。