hdu 5015(マトリクスの高速べき乗)
3840 ワード
テーマリンク: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):823 Acceepted Submission(s):493
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
233 Matrix
Time Limit:10000/5000 MS(Java/Others) メモリLimit:65536/65536 K(Java/Others)Total Submission(s):823 Acceepted Submission(s):493
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
Source
2014 ACM/ICPC Asia Regional Xi'an Online
Recommend
hujie | We have carefully selected several similar problems for you: 5041 5040 5039 5038 5037
思路：矩阵快速幂，由第一列推出剩下的列~有点得注意，要用I64d,如果用int 会wrong~~~可以从题目给的时间5000ms和题目给的数据看很出来~
#include
#include
#include
#include
#include
#include
const int mod=10000007;
typedef long long ll;
using namespace std;
int a[12];
struct matrix
{
ll f[12][12];
};
// ;
matrix mul(matrix a,matrix b)
{
matrix c;
memset(c.f,0,sizeof(c.f));
for(int i=0;i<12;i++)
for(int j=0;j<12;j++)
for(int k=0;k<12;k++)
{
c.f[i][j]+=a.f[i][k]*b.f[k][j]%mod; // ， mod
c.f[i][j]%=mod;
}
return c;
}
matrix pow_mod(matrix a,int b)
{
matrix s;
memset(s.f,0,sizeof(s.f));
for(int i=0;i<12;i++)
s.f[i][i]=1;
while(b)
{
if(b&1)
{
s=mul(s,a);
}
b=b/2;
a=mul(a,a);
}
return s;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
matrix e;
memset(e.f,0,sizeof(e.f));
for(int i=1;i<11;i++)
for(int j=0;j<=i;j++)
e.f[i][j]=1;
e.f[0][0]=10; e.f[0][11]=1,e.f[11][11]=1;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)cin>>a[i];
a[0]=233,a[11]=3;
e=pow_mod(e,m);
ll sum=0;
for(int i=0;i<12;i++)
{
sum=(sum+(e.f[n][i]*a[i]))%mod;
}
printf("%I64d
",sum%mod);
}
return 0;
}