学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5015

题目的意思是：

n*m的矩阵 n<= 10, m <= 10^9。。求第n行m列的元素。。

第0行第0个元素为空的，第一个位233，第二个2333，23333，23333......等等。

第0列第一个为a1，第二个为a2，第三个为a3.......等等。。

然后就需要计算出个矩阵的第n行第m列的元素 mod 10000007。。

其实，矩阵做到现在就是这样的特征，大数据+取模。。然后你只需要从第一个状态矩阵推到第二个状态矩阵，并构造出状态转移矩阵。。。那么就ok了。。矩阵乘法快速幂就ok了。。

再有点意思是就是再给你杂糅一种其他算法或这数据结构。。。。

再往后......  水平还没有达到再往后的程度。。。。

跑题了。。 - -     继续说这个问题。

这个问题的话，我们就从第一列向第二列推。。为什么？？？

这还用问吗?  因为，行数是小的。。 n<= 10。嘛。。也就是状态矩阵最多12维。。。这是我的状态转移矩阵的维数。。不同的状态转移方程会有不同的维数。。

状态转移矩阵code 中看。。。A

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define INT __int64

const int N = 15;
const INT mod = 10000007;
struct Matrix
{
    int n, m;
    INT a[N][N];
    void Init(){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++)
            a[i][j] = 0;
        }
    }
    void Unit(){
        for(int i = 1; i <= n; i ++)
        a[i][i] = 1;
    }
};

Matrix operator * (Matrix a, Matrix b)
{
    Matrix ans;
    ans.n = a.n; ans.m = b.m;
    ans.Init();
    for(int i = 1; i <= a.n; i ++){
        for(int j = 1; j <= b.m; j ++){
            for(int k = 1; k <= b.n; k ++){
                ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
            }
        }
    }
    return ans;
}

Matrix power(Matrix ans, Matrix A, int k)
{
    while(k){
        if(k & 1) ans = ans * A;
        A = A * A;
        k = k >> 1;
    }
    return ans;
}

int main()
{
    int n, m;
    while(~scanf("%d %d", &n, &m)){
        Matrix ans;
        ans.n = 1; ans.m = n + 2;
        ans.a[1][1] = 233; ans.a[1][2] = 1;
        for(int i = 1; i <= n; i ++){
            scanf("%I64d", &ans.a[1][i + 2]);
        }
        Matrix A;
        A.n = n + 2; A.m = n + 2;
        A.Init();
        A.a[1][1] = 10; A.a[2][1] = 3;
        A.a[2][2] = 1;
        for(int i = 3; i <= A.m; i ++){
            for(int j = 1; j <= i; j ++){
                if(j == 2) continue;
                A.a[j][i] = 1;
            }
        }
        ans = power(ans, A, m);
        printf("%I64d\n", ans.a[1][n + 2]);
    }
    return 0;
}

------->

10+分钟写完，没有编译错误，样例测试对，直接交，AC。perfect。完美。。

只是，现场上，我猜也不会出这么简单的矩阵题目。。出也会出那种各种算法和数据结构杂糅在一起的。。。而，这正是我们所欠缺的。。。

最近状态不是太好，也不知道怎么回事，我想应该不会持续太长的时间。。。

我觉的据北京赛区的时间还有20 + 天，应该好好的有个计划。。否者这是要挂的节奏。。这是我们都不想看到的结果。。

如果你想要达到你所想要的，你必须得让他有点理由吧。。。。也就是说，你必须有一点准备。。。上天不会眷顾没有准备的孩子的，不是吗？

那就写计划吧，记录。。这不是我一贯的做法吗？？？