首页 > ACM题库 > HDU-杭电 > HDU 3493-The Little Architect-快速幂-[解题报告]HOJ
2014
04-04

HDU 3493-The Little Architect-快速幂-[解题报告]HOJ

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:

Segment

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


Hint
When n = 3, there are 6 different buildings like these:
Segment

下面是 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;
}

参考:http://blog.csdn.net/weiguang_123/article/details/7990084


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