2014
04-04

# The Little Architect

LY is a little architect, he likes to make all kinds of buildings with his building blocks. All the building blocks are the same cubes. Now he want to make a new building. He don’t want any floor of his building is disconnected. So sample of the building he likes and he dislikes like these:

The building he likes. The building he dislikes.

For example, the first building he likes because all the blocks in every line are not disconnected, while the second building he dislikes because in line 1, 3, 4, the blocks are disconnected.
Now LY has a question. If he has n building blocks, and how many different buildings he can build. We ensure that all the building blocks are in the same plane.

There are several lines in the input. Each line is a set of input data. There is only one integer n (0 < n < 1,000,000,000) means the number of blocks buildings he has. The last line of the input is a line contains 0.

There are several lines in the input. Each line is a set of input data. There is only one integer n (0 < n < 1,000,000,000) means the number of blocks buildings he has. The last line of the input is a line contains 0.

1
2
3
4
20
0

1
2
6
19
2840

HintWhen n = 3, there are 6 different buildings like these:



下面是 m^n % k 的快速幂：
// m^n % k
int quickpow(int m,int n,int k)
{
int b = 1;
while (n > 0)
{
if (n & 1)
b = (b*m)%k;
n = n >> 1 ;
m = (m*m)%k;
}
return b;
}

//HOJ 3493
/*===================================*/
|| 快速幂（quickpow）模板
|| P 为等比，I 为单位矩阵
|| MAX 要初始化！！！！
||
/*===================================*/
/*****************************************************/
#include <cstdio>
const int MAX = 3;

typedef struct
{
int m[MAX][MAX];
} Matrix;

Matrix P = {5,-7,4,
1,0,0,
0,1,0,
};

Matrix I = {1,0,0,
0,1,0,
0,0,1,
};

Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
{
int i,j,k;
Matrix c;
for (i = 0 ; i < MAX; i++)
for (j = 0; j < MAX; j++)
{
c.m[i][j] = 0;
for (k = 0; k < MAX; k++)
c.m[i][j] += (a.m[i][k] * b.m[k][j])%9997;
c.m[i][j] %= 9997;
}
return c;
}

Matrix quickpow(long long n)
{
Matrix m = P, b = I;
while (n >= 1)
{
if (n & 1)
b = matrixmul(b,m);
n = n >> 1;
m = matrixmul(m,m);
}
return b;
}
/*************************************/

int main()
{
Matrix re;
int f[3] = {2,6,19};
long long n;
while (scanf("%I64d",&n) && n != 0)
{
if (n == 1)
printf("1\n");
else if (n <= 4)
printf("%d\n",f[n-2]);
else
{
re = quickpow(n - 4);
printf("%d\n",(((re.m[0][0]*f[2])
+ (re.m[0][1]*f[1]) + (re.m[0][2]*f[0])) %9997 + 9997) % 9997);
}
}
return 0;
}


1. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？