这道题目的意思是：一开始有一个数字 1 ，在接下来的时间中，计算机会按照如下规则进行扩展：
0 –> 1 0
1 –> 0 1
求n秒之后，有多少对相邻的0。 例如1 0 0 1有 1 对相邻的0.
这道题目是一道规律题，可以直接例举前面的数据得到规律：
0 0 1 1 3 5 11 21 43 85
通过例举的数据可以很明显的看出，从第 1s 开始，如果是偶数秒，那么b[ i ] = b[ i – 1 ] * 2 – 1，而奇数秒则是b[ i ] = b[ i – 1 ] * 2 + 1。于是可以预处理打表得出0 ~ 1000的结果。
需要注意的是，这道题需要用到高精度，因为最大的值约为 2 ^ 1000，这个数非常大。
附AC代码：
1: #include <iostream>
2: #include <string>
3: #include <algorithm>
4: using namespace std;
5:
6: int s[1005][505];
7: int num, temp = 0;
8:
9: int main()
10: {
11: s[0][1] = 0;
12: s[1][1] = 0;
13: s[2][1] = 1;
14: s[3][1] = 1;
15: for(int i = 4; i <= 1000; ++i)
16: {
17: for(int j = 1; j <= 500; ++j)
18: {
19: s[i][j] = s[i - 1][j] + 2 * s[i - 2][j] + temp;
20: temp = s[i][j] / 10;
21: s[i][j] %= 10;
22: }
23: }
24: while(~scanf("%d", &num))
25: {
26: if(num == 1)
27: puts("0");
28: else
29: {
30: int i;
31: for(i = 500; i > 0; --i)
32: if(s[num][i] != 0)
33: break;
34: for(int j = i; j >= 1; --j)
35: printf("%d", s[num][j]);
36: puts("");
37: }
38: }
39: return 0;
40: }