https://www.luogu.com.cn/problem/P3390
- 把*重载成矩阵的乘法
- 再用普通的快速幂就行
- (AC代码是copy的,实在debug不出了)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#define ll long long
#define gc() getchar()
#define maxn 105
#define mo 1000000007
using namespace std;
inline ll read()
{
ll a = 0;
int f = 0;
char p = gc();
while (!isdigit(p))
{
f |= p == '-';
p = gc();
}
while (isdigit(p))
{
a = (a << 3) + (a << 1) + (p ^ 48);
p = gc();
}
return f ? -a : a;
}
int n;
struct ahaha
{
ll a[maxn][maxn];
ahaha()
{
memset(a, 0, sizeof a);
}
inline void build()
{ //建造单位矩阵
for (int i = 1; i <= n; ++i)
a[i][i] = 1;
}
} a;
ahaha operator*(const ahaha &x, const ahaha &y)
{
ahaha z;
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % mo) % mo;
return z;
}
ll k;
inline void init()
{
n = read();
k = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
a.a[i][j] = read();
}
int main()
{
init();
ahaha ans;
ans.build();
do
{
if (k & 1)
ans = ans * a;
a = a * a;
k >>= 1;
} while (k);
for (int i = 1; i <= n; putchar('/n'), ++i)
for (int j = 1; j <= n; ++j)
printf("%d ", ans.a[i][j]);
return 0;
}
原创文章,作者:Carrie001128,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/277990.html