紫书 例题8-12 UVa 12627 （找规律 + 递归）
紫书上有很明显的笔误， 公式写错了。g（k， i）的那个公式应该加上c（k-1）而不是c（k）。如果加上c（k-1）那就是这一次
所有的红气球的数目， 肯定大于最下面i行的红气球数
我用的是f的公式， 我觉得这个稍微比f好理解一点。f（k， i） 表示k小时之后最上面i行红气球的个数。
分两种情况
如图所示
左上角的正方形的上面i行的红气球个数和前一个小时（也就是k-1）的整个正方形的上面i行的红气球个数是一样的， 因为右上角还有一个， 所以要乘2， 也就是f(k - 1, i) = 2 * f(k - 1, i)
上面两个四分之一正方形是占满的了， 所以就是c(k - 1)， c（k）表示k小时后所有红气球的个数， c（k） = 3的k次方
下面多出来一块， 而右下角那一块全是蓝气球， 不理它。左下角这一块有f(k - 1, i - k1)个， i-k1表示多出来的长度
所以f(k - 1, i) = f(k - 1, i - k1) + 2 * c(k - 1)
临界条件k=0的时候有一个红气球， i=0的时候没有红气球
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
typedef long long ll;
ll c(int x) { return x == 0 ? 1 : 3 * c(x - 1); }
ll f(int k, int i)
{
if(i == 0) return 0;
if(k == 0) return 1;
int k1 = 1 << (k - 1);
if(i >= k1) return f(k - 1, i - k1) + 2 * c(k - 1);
else return 2 * f(k - 1, i);
}
int main()
{
int T, k, a, b;
scanf("%d", &T);
REP(kase, 1, T + 1)
{
scanf("%d%d%d", &k, &a, &b);
printf("Case %d: %lld
", kase, f(k, b) - f(k, a - 1));
}
return 0;
}