UVA 12627 气球胀啊胀

题目在此

题意：第0个小时有一个红气球，每过一个小时，一个红气球膨胀为3个红球和1个蓝球
一个蓝球膨胀为4个蓝球，排成下图的样子，问过了k小时，第a行到第b行有多少个红球

看下题目里的图，把每个图十字分开，就很容易发现k和k+1的关系
除了右下角全是蓝色以外，剩下都是复制

f[k][i] 表示第k个小时，前i行有多少个红球
当i在上半区（1到(1<<(k-1))行）的时候，气球是复制的k-1的状态，只需 *2即可
。。。下。。。。。。，把上半区的全加上，再加上k-1时前（i-上半区行数）行的气球
c[k]=第k个小时红色气球总数

答案输出f[k][b]-f[k][a-1]即可

#include<cstdio>
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N=40000;
int i,k,a,b;
LL c[40];

LL f(int k,int i){
    if (i<=0)return 0;
    if (k==0)return 1;
    if (i<=(1<<(k-1)))return f(k-1,i)<<1;
    return c[k-1]*2+f(k-1,i-(1<<(k-1)));
}

int main(){
    //freopen("fuck.in","r",stdin);
    int T;scanf("%d",&T);
    c[0]=1;for (int i=1;i<=31;i++)c[i]=c[i-1]*3;
    for (int cas=1;cas<=T;cas++){
        scanf("%d%d%d",&k,&a,&b);
        printf("Case %d: %lld\n",cas,f(k,b)-f(k,a-1));
    }
    return 0;
}