题意就不说了，中文题。。。
小白上讲了棋盘覆盖，于是我就挖了这题来做。
棋盘覆盖的推导不是很难理解，就是分治的思想，具体可以去谷歌下。
公式就是f(k) = f(k - 1) * 4 + 1，再化解下就是4^0 + 4^1 + 4^2 + ... + 4^(n-1)。
思路很简单，但是题目没想象中的简单，刚开始天真的用递归模拟了下就交上去，立马wa掉。。。
发现即使用Long long类型，n到32就挂了 +_+。。。
于是实在不是很懂，难道一定要用高精度吗？贵了好久，最后只得找到一篇题解来理解，顺便学了一下万进制，很神奇的高精度～
虽然跪了，但收获还是蛮大的。看讨论里面说数据只有100，表示不想作弊。。。
代码：
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: 45.cpp
* Lauguage: C/C++
* Create Date: 2013-08-31 19:39:38
* Descripton: nyoj 45, cheesboard coverage, wan jin zhi
*/
#include <cstdio> const int MAXN = 100;
int a[MAXN]; // 万进制，每位存4进制 int main() {
int n, m, c;
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
if (m == 1) {
printf("1\n");
continue;
}
a[0] = 1;
int t = 0; // 已经用到第几位
for (int i = 1; i < m; i++) {
c = 0; // c为进位数
for (int j = 0; j <= t; j++) {
a[j] = a[j] * 4 + c;
c = a[j] / 10000;
a[j] %= 10000;
}
if (c != 0) {
t++;
a[t] = c;
}
a[0]++;
}
// 处理最后的进位，其实就是99999999这种情况，这里可以不用
// for (int j = 0; j <= t; j++) {
// c = a[j] / 10000;
// a[j] %= 10000;
// }
// if (c != 0) {
// t++;
// a[t] = c;
// }
printf("%d", a[t]);
for (int i = t - 1; i >= 0; i--)
printf("%04d", a[i]);
printf("\n");
}
return 0;
}