例题 8-12 奇怪的气球膨胀（Erratic Expansion, UVa12627）

原题链接：https://vjudge.net/problem/UVA-12627
分类：公式推理
备注：前缀和,递归

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,k,a,b;
ll f(int k,ll i){
    if(i==0)return 0;
    if(k==0)return 1;
    if(k==1)return i?i+1:0;
    if(i>=(1<<(k-1)))return 2ll*pow(3ll,k-1)+f(k-1,i-(1<<(k-1)));
    return 2ll*f(k-1,i);
}
int main(void){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d %d %d",&k,&a,&b);
        printf("Case %d: %lld\n",i,f(k,b)-f(k,a-1));
    }
    return 0;
}