hdu 5015(行列高速べき乗)
住所:http://acm.hdu.edu.cn/showproblem.php?pid=5015
233 Matrix
Time Limit:10000/5000 MS(Java/Others) メモリLimit:65536/65536 K(Java/Others)Total Submission(s):855 Acceepted Submission(s):514
Problem Description
In our daily life we offten use 233 to express our feelings.Actualy,we may say 2333,or 23333...in the same meaning.And here is the question:Suppose we have a matrix caled 233.Inthers filt 233
0,1 = 233,a
0,2 = 2333,a
0,3 = 23333…)Besides、in 233 matix、we got a
i,j = a.
i-1,j +a.
i,j-1(i,j≠0).Now you have known a
1,0,a
2,0,…,a
n,0,could you tell me a
n,m in the 233 matrix
Input
The re are multiple test cases.Please process till EOF.
For each case,the first line contains two postive integers n,m(n≦10,m≦10
9)The second line contains n integers、a
1,0,a
2,0,…,a
n,0(0≦a
i,0 < 2
31)
Output
For each case,output a
n,m mod 100000.
Sample Input
题意：有一个从（0,0）点开始(n+1)*(m+1)的矩阵，其（0,i）点的格式为233……3（其中有i+1个3，i从1开始），其（i,0）点依次输入进去，然后剩下的点位该点前边的点与上面的点之和，问该矩阵右下角的点的值。
233 Matrix
Time Limit:10000/5000 MS(Java/Others) メモリLimit:65536/65536 K(Java/Others)Total Submission(s):855 Acceepted Submission(s):514
Problem Description
In our daily life we offten use 233 to express our feelings.Actualy,we may say 2333,or 23333...in the same meaning.And here is the question:Suppose we have a matrix caled 233.Inthers filt 233
0,1 = 233,a
0,2 = 2333,a
0,3 = 23333…)Besides、in 233 matix、we got a
i,j = a.
i-1,j +a.
i,j-1(i,j≠0).Now you have known a
1,0,a
2,0,…,a
n,0,could you tell me a
n,m in the 233 matrix
Input
The re are multiple test cases.Please process till EOF.
For each case,the first line contains two postive integers n,m(n≦10,m≦10
9)The second line contains n integers、a
1,0,a
2,0,…,a
n,0(0≦a
i,0 < 2
31)
Output
For each case,output a
n,m mod 100000.
Sample Input
1 1 1 2 2 0 0 3 7 23 47 16
Sample Output
234 2799 72937Hint
思路：很明显的矩阵快速幂，推出矩阵后就好些了。
代码：
/***************************************************
***************************************************/
#include
#include
#include
#include
using namespace std;
#define LL __int64
#define Mod 10000007
struct Mat {
LL mat[15][15];
void cle(){
memset(mat,0,sizeof(mat));
}
}two,three;
int m,n;
Mat operator * (Mat a, Mat b) { //
Mat c;
c.cle(); // c
for(int k = 0; k <= m+1; ++k) { //
for(int i = 0; i <= m+1; ++i) {
if(a.mat[i][k] <= 0) continue;
for(int j = 0; j <= m+1; ++j) {
if(b.mat[k][j] <= 0) continue;
c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
if(c.mat[i][j]>Mod) c.mat[i][j]%=Mod; // mod mod
}
}
}
return c;
}
int main(){
while(scanf("%d%d",&m,&n)>0){
two.cle();
three.cle();
two.mat[0][0]=233;
two.mat[0][m+1]=3;
for(int i=1;i<=m;i++)
scanf("%d",&two.mat[0][i]);
for(int i=0;i<=m;i++)
for(int j=i;j<=m;j++)
three.mat[i][j]=1;
three.mat[0][0]=10;
three.mat[m+1][0]=1;
three.mat[m+1][m+1]=1;
while(n){
if(1&n){
two=two*three;
}
three=three*three;
n/=2;
}
printf("%I64d
",two.mat[0][m]);
}
return 0;
}