UVa12627 Erratic Expansion（递归/找规律）

题目链接

1.初始有一个红气球，每过一个小时，一个红气球会变成3个红气球和1个蓝气球，一个蓝气球会变成4个蓝气球，如图所示。初始有一个红气球，求经过k个小时以后，第A行到第B行一共有多少个红气球

2.一看就是找规律的题目嘛，本来想到的是记录每行红气球的变化，确实有规律，但是必须由前一个状态求得，而且要用数组记录，但是看了一下k的范围，最大是30的话是1e9，显然数组开不了那么大。看了一下LRJ的分析，是按照前i行的红气球总数来找规律的，类似于前缀和区间[L,R]，即f( R )-f(L-1)。那么这样找一下规律后：

3.设f(k,i)表示k小时后，第i行之前的红气球个数之和。那么我们不难得到:
当i<=2^k-1时，f(k,i)=2*f(k-1,i)
当i>2^k-1时，f(k,i)=f(k,2^k-1)+f(k-1,i-2^k-1)
注意到当i为0时直接返回0，当k为0时返回1

4.但是这样写却超时了！因为下面f(k,2^k-1)相当于每个数都算了两遍，因此得想办法更快的，注意到f(k,2^k-1)=2*f(k-1,2^k-1)，且都是上个状态的最后一个数，那么不难发现1,3,9,27…，则最后一行可以直接由3^k推导得到，最后再乘2即可

#include <iostream>
using namespace std;
typedef long long ll;

ll quick_pow(ll x,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans*=x;
        x*=x;
        n>>=1;
    }
    return ans;
}

ll f(int k,int i){
    if(i==0) return 0;
    if(k==0) return 1;
    ll x=1<<(k-1);
    if(i<=x) return 2*f(k-1,i);
    else return 2*quick_pow(3,k-1)+f(k-1,i-x);
    //else return f(k,x)+f(k-1,i-x);
}

int main()
{
    int t,k,a,b,kase=0;
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>k>>a>>b;
        cout<<"Case "<<++kase<<": "<<f(k,b)-f(k,a-1)<<endl;
    }
    return 0;
}