矩阵快速幂-233 Matrix HDU - 5015
程序员文章站
2022-07-03 18:25:10
...
矩阵快速幂-233 Matrix HDU - 5015
题目:
wbx定义了一种新的矩阵,它的第一行是这样一些数:(a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333…) 除此之外,在这个矩阵里, 我们有 a i,j = a i-1,j +a i,j-1( i,j ≠ 0).现在给你 a 1,0,a 2,0,…,a n,0, 你能告诉wbx,a n,m 是多少吗?
Input
多组数据。
每一组数据第一行有两个正整数 n,m(n ≤ 10,m ≤ 10 9). 第二行是n个整数a 1,0,a 2,0,…,a n,0(0 ≤ a i,0 < 2 31).
Output
输出 a n,m mod 10000007.
Sample Input
1 1
1
2 2
0 0
3 7
23 47 16
Sample Output
234
2799
72937
题意:
给出矩阵第0行,第1~n列的初始值(分别是233,2333,23333,…)
给出递推公式:a(i,j)=a(i-1,j)+a(i,j-1)
现输入矩阵行数n,列数m,以及第1列,第1~n行的初始值,求出a(n,m)的值
题解:
首先构造出关系矩阵
根据已给出的初始值容易看出,后一列第0行的值是前一列第0行的值的10倍+3,那么可得a(0,0)=23,构造a(0,n+1)=3最后加上。
于是初始矩阵第一列的值如下:
可以确定第一列的值为10的n+1行的矩阵,因此该关系矩阵最后一列的值应该为1。
再根据递推式可得关系矩阵。
关系矩阵如图:
那么求出关系矩阵Gm再乘初始矩阵的第一列即可。
代码:
#include <iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod=1e7+7 , N=15;
int n,m;
ll rec[N];//初始序列
ll ans=0;
void mat_mul(ll a[N][N],ll b[N][N])
{
ll c[N][N];
memset(c,0,sizeof(c));
for(int k=0;k<=n+1;k++)
for(int i=0;i<=n+1;i++)
for(int j=0;j<=n+1;j++)
c[i][j]=((c[i][j]+a[i][k]*b[k][j])%mod+mod)%mod;
memcpy(a,c,sizeof(c));
}
void mat_pow(int k)
{
ll M[N][N];//关系矩阵M
memset(M,0,sizeof(M));//不可少!!!
for(int i=0;i<=n;i++)//初始化
{
M[i][0]=10;
M[i][n+1]=1;
for(int j=1;j<i+1;j++)
M[i][j]=1;
}
//将n+1列变成1
M[n+1][n+1]=1;
//矩阵快速幂
ll E[N][N];//单位矩阵
memset(E,0,sizeof(E));
for(int i=0;i<=n+1;i++) E[i][i]=1;
while(k)
{
if(k&1) mat_mul(E,M);
mat_mul(M,M);
k>>=1;
}
//最后将k次方关系矩阵E与初始序列rec相乘
for(int i=0;i<=n+1;i++)
ans=(ans+E[n][i]*rec[i])%mod;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
ans=0;
rec[0]=23;
rec[n+1]=3;
for(int i=1;i<=n;i++)
scanf("%d",&rec[i]);
mat_pow(m);
printf("%d\n",ans);
}
return 0;
}
总结:
数组开局部变量要注意初始化
推荐阅读
-
HDU 2256Problem of Precision(矩阵快速幂)
-
POJ3233Matrix Power Series(矩阵快速幂)
-
Recursive sequence(HDU5950 矩阵快速幂)
-
hdu4990——多解矩阵快速幂
-
hdu4990矩阵快速幂
-
HDU4990 Reading comprehension【矩阵快速幂】
-
HDU4990 Reading comprehension【矩阵快速幂】
-
HDU 2256Problem of Precision(矩阵快速幂)
-
hdu 5015 矩阵快速幂
-
矩阵快速幂专题 HDU1757 HDU1575 HDU2604 HDU2256 CF185A HDU2276 HDU2842