本文主要是介绍Hdu 5015 233 Matrix[矩阵](2014 ACM/ICPC Asia Regional Xi'an Online )，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：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 __int64const 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 + 天，应该好好的有个计划。。否者这是要挂的节奏。。这是我们都不想看到的结果。。
如果你想要达到你所想要的，你必须得让他有点理由吧。。。。也就是说，你必须有一点准备。。。上天不会眷顾没有准备的孩子的，不是吗？
那就写计划吧，记录。。这不是我一贯的做法吗？？？
这篇关于Hdu 5015 233 Matrix[矩阵](2014 ACM/ICPC Asia Regional Xi'an Online )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
