hdu 5015 大数量反复类似操作问题/ 矩阵高速幂

时间:2022-02-09 07:12:14

题意: 给一个矩阵a,第一行是 0。 233,2333,23333.....第一列读入。列数<10^9.行数<=10.

先转化操作: m是大数量。必定每次向前推一列。就是每次乘一个矩阵T。就推一列,画画草稿自热而然就想到了。

转化阵T(n+2*n+2)和初始矩阵A(n+2*1 ):

T={ 1,0,0,0,0,0,0,0,0,0...10,1
1 1 0 0 0 0 0 0 0 0 10 1
1 1 1 0 0 0 0 0 0 0 10 1
1 1 1 1 0 0 0 0 0 0 10 1
...
1 1 1 1 1 1 1 1 1 1 10 1
0 0 0 0 0 0 0 0 0 0 10 1
0 0 0 0 0 0 0 0 0 0 0 1
}
A={ a1
a2
.
.
.
23
3
}
#include<iostream>
#include<cstring>
using namespace std;
struct juz
{
long long bat[15][15];
int x,y; //行 列
juz ()
{
memset(bat,0,sizeof(bat));
x=0;y=0;
}
};
juz mutp(juz a,juz b)
{
juz c;
c.x=a.x;c.y=b.y;
memset(c.bat,0,sizeof(c.bat));
for(int k=0;k<a.y;k++)
for(int i=0;i<a.x;i++)
if(a.bat[i][k])
{
for(int j=0;j<b.y;j++)
{
c.bat[i][j]=(c.bat[i][j]+(a.bat[i][k]*b.bat[k][j])%10000007)%10000007;
}
}
return c;
}
juz quickf(juz a,int k)
{
juz c=a;
for(int i=0;i<a.x;i++)
for(int j=0;j<a.x;j++)
c.bat[i][j]=(i==j);
while(k>=1)
{
if(k%2)
c=mutp(c,a);
k=k/2; a=mutp(a,a);
}
return c;
}
int main()
{
int n,m,k;
while(cin>>n>>m)
{
juz a,b,c;
a.x=n+2;a.y=1; b.x=n+2;b.y=n+2;
for(int i=0;i<n;i++)
{
cin>>a.bat[i][0];
}
a.bat[n][0]=23; a.bat[n+1][0]=3;
for(int i=0;i<n+2;i++)
for(int j=0;j<n+2;j++)
{
if(i>=j&&i<n)
b.bat[i][j]=1;
else
b.bat[i][j]=0;
if(j==n&&i!=n+1)
b.bat[i][j]=10;
if(j==n&&i==n+1)
b.bat[i][j]=0;
if(j==n+1)
b.bat[i][j]=1;
}
c=quickf(b,m);
c=mutp(c,a);
cout<<c.bat[n-1][0]<<endl;
}
return 0;
}