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