div code ast 输入 pac can pre def
矩阵快速幂
给定 n*n 的矩阵 A,求 A^k
输入格式:
第一行,n,k
第 2 至 n+1 行,每行 n 个数,第 i+1 行第 j 个数表示矩阵第 i 行第 j 列的元素
输出格式:
输出 A^k
共 n 行,每行 n 个数,第 i 行第 j 个数表示矩阵第 i 行第 j 列的元素,每个元素模 10^9+7
- 2 1
- 1 1
- 1 1
- 1 1
- 1 1
n<=100, k<=10^12, | 矩阵元素 |<=1000 算法:矩阵快速幂
- #include <cstdio>
- #include <iostream>
- using namespace std;
- typedef long long ll;
- ll x[999][999];
- ll ans[999][999];
- ll dx[999][999];
- const int p=1e9+7;
- inline void anscf(int n)
- {
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- dx[i][j]=ans[i][j],ans[i][j]=0;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- for(int k=1;k<=n;k++)
- ans[i][j]=(ans[i][j]+(x[i][k]*dx[k][j])%p)%p;
- }
- inline void xcf(int n)
- {
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- dx[i][j]=x[i][j],x[i][j]=0;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- for(int k=1;k<=n;k++)
- x[i][j]=(x[i][j]+(dx[i][k]*dx[k][j])%p)%p;
- }
- inline void fastpow(ll n,ll w)
- {
- while(w)
- {
- if(w%2==1) anscf(n);
- w/=2;
- xcf(n);
- }
- }
- int main()
- {
- ll n,k;
- scanf("%lld%lld",&n,&k);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- scanf("%d",&x[i][j]),ans[i][j]=x[i][j];
- fastpow(n,k-1);
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- printf("%lld ",ans[i][j]);
- puts("");
- }
- }
Luogu P3390 【模板】矩阵快速幂
来源: http://www.bubuko.com/infodetail-2275361.html