牛客动态规划训练

#include<iostream>
using namespace std;

int t;
long long f[100];

void init()
{
    
    f[1]=1;
    f[2]=2;
    for(int i=3;i<=80;i++)
    {
    
        f[i]=f[i-1]+f[i-2];
    }
}

int main()
{
    
    init();
    cin>>t;
    int n;
    while(t--)
    {
    
        scanf("%d",&n);
        printf("%lld\n",f[n]);
    }
    return 0;
}

#include<iostream>
using namespace std;

const int mod=1e9+7;
int t;
int f[100010];

int main()
{
    
    cin>>t;
    int n;
    f[1]=3;
    f[2]=9;
    while(t--)
    {
    
        scanf("%d",&n);
        for(int i=3;i<=n;i++)
        {
    
            f[i]=(2*((f[i-1]+f[i-2])%mod))%mod;
        }
        printf("%d\n",f[n]);
    }
    return 0;
}

#include<iostream>
using namespace std;

int t;

long long f(long long n)
{
    
    if(n<=2) return 0;
    else if(n==3) return 1;
    else
    {
    
        if(n%2==0) return 2*f(n/2);
        else return f(n/2)+f(n/2+1)+1;
    }
}


int main()
{
    
    cin>>t;
    long long n;
    while(t--)
    {
    
        scanf("%lld",&n);
        printf("%lld\n",f(n));
    }
    return 0;
}