233 Matrix
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 553 Accepted Submission(s): 345
Problem Description
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a0,1 = 233,a0,2 = 2333,a0,3 = 23333...) Besides, in 233 matrix, we got ai,j = ai-1,j +ai,j-1( i,j ≠ 0). Now you have known a1,0,a2,0,...,an,0, could you tell me an,m in the 233 matrix?
Input
There are multiple test cases. Please process till EOF.
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 109). The second line contains n integers, a1,0,a2,0,...,an,0(0 ≤ ai,0 < 231).
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 109). The second line contains n integers, a1,0,a2,0,...,an,0(0 ≤ ai,0 < 231).
Output
For each case, output an,m mod 10000007.
Sample Input
1 1
1
2 2
0 0
3 7
23 47 16
Sample Output
234
2799
72937
Hint
题意:
有个 N 行 M 列的矩阵,给出第一行和第一列的元素,根据 a [ i ] [ j ] = a [ i - 1 ] [ j ] + a [ i ] [ j - 1 ] 求出 a [ n ] [ m ] 元素是什么。
思路:
矩阵快速幂。详细题解明天再补回。记得要用 long long。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; const ll MOD = 10000007; ll n, m; mat mul (mat a, mat b) { mat c(n + 2, vec(n + 2)); for (ll i = 0; i < n + 2; ++i) { for (ll j = 0; j < n + 2; ++j) { for (ll k = 0; k < n + 2; ++k) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD; } } } return c; } mat pow (mat a) { mat b(n + 2, vec(n + 2)); for (ll i = 0; i < n + 2; ++i) { b[i][i] = 1; } while (m > 0) { if (m & 1) b = mul(b, a); a = mul(a, a); m >>= 1; } return b; } int main () { while (~scanf("%I64d%I64d", &n, &m)) { mat a(n + 2, vec(n + 2)); mat b(n + 2, vec(1)); a[0][0] = 10, a[0][1] = a[1][1] = 1; for (ll i = 2; i < n + 2; ++i) { for (ll j = 0; j < n + 2; ++j) { if (j <= i) a[i][j] = 1; if (!j) a[i][j] = 10; } } b[0][0] = 23, b[1][0] = 3; for (ll i = 0; i < n; ++i) { scanf("%I64d", &b[i + 2][0]); b[i + 2][0] %= MOD; } a = pow(a); b = mul(a, b); printf("%I64d\n", b[n + 1][0]); } return 0; }
相关推荐
别再下载这个了,我都觉得丢人,请使用math.net #这是自己编的矩阵类,所有的输入矩阵都是二维矩阵。#
essential matrix 本质矩阵essential matrix 本质矩阵essential matrix 本质矩阵
Android Matrix矩阵的使用及测试样例源码下载,定义一个等比例绽放的图像矩阵,并可以倾斜的矩阵。
Matrix矩阵类.doc
matrix矩阵类的文档,矩阵操作的说明文件。可以添加为基础类,进行调用操作
Adroid Matrix 矩阵
android matrix 矩阵变换 set pre post 区别
矩阵运算类的实现源码,包括矩阵加减法,乘法,矩阵求逆,转置
1. 矩阵加法、减法、乘法和数乘运算 2. 矩阵求秩 3. 矩阵QR分解 4. 矩阵行列式和求逆 [由于使用double做为基本类型,运算后对误差会进行过滤操作(可调整)] 5. 矩阵转置 6. 矩阵大小设置 7. 矩阵元素输入...
自己编写的matrix矩阵类 可以实现矩阵的加减法、乘法、求逆 求逆采用lup算法
Pelco_CM6800_32x6_Matrix矩阵切换器控制器汇编.pdf
Matrix Analysis
Matlab-matrix 介绍 2020年矩阵与数值分析上机实验,MATLAB实现。 2.1 GaussElimination.m实现了高斯消去法求解方程组 L_GaussElimination.m实现了带列主元的高斯消去法求解方程组 LU.m实现了LU分解 LUP.m实现了带...
自己写的 MATRIX 类,V0,3 版本。 定义了矩阵之间的 加,减,乘 矩阵和实数间的 加,减,乘,除 包括 LU 分解,列主元 LU 分解,Cholesky 分解 改进的 Cholesky 分解算法存在问题,需要修正 重载很多运算符,比如...
矩阵实现visual c++ 环境 矩阵实现 c语言
.net 矩阵运算类库,来自http://www.aisto.com/roeder/dotnet 有各种矩阵操作.
matrix_operator 矩阵求幂
这是一本很好的矩阵计算书,是研究数值计算方向的一本很好的工具书
网络上的Matrix运算库繁多,但有很多功能不够完整,或缺少注释,给使用者带来不少麻烦。该函数库是我搜集到的比较全面的矩阵运算库,而且附带引自清华大学bbs上的函数功能注释,使用方便。 内容包括: Matrix.cpp ...
Matrix_Theory,国外矩阵论教材