Warning: session_start(): open(/tmp/sess_f9b0d6cb0843342a6d698f4a65883dad, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020/07/25--2020/07/31====== ---- ===== 团队训练 ===== 暂无 ---- ===== 王瑞琦 ===== ===比赛=== 无 ===专题=== 无 ===== 冯宇扬 ===== ===比赛=== cf 659 div 2\\ [[2020-2021:teams:no_morning_training:fayuanyu:cf_r660d2|cf 660 div 2]] ===== 常程 ===== ===比赛=== 无 ===专题=== 摸了 ---- ===== 本周推荐 ===== ==== 王瑞琦 ==== 写了一道矩阵快速幂的模板题。 ===来源=== 洛谷P3390：[[https://www.luogu.com.cn/problem/P3390|【模板】矩阵快速幂]] ===标签=== 数学，矩阵乘法 ===题意=== 给出一个n*n的矩阵，计算其的k次方 ===题解=== 对矩阵运用快速幂=。=\\ 快速幂：\\ 对于n的k次方，可以不需要计算k次，只需计算出n^(k/2)，然后再开方即可（对于k为奇的情况要再乘一个n）\\ 可以将复杂度降到O(logn)\\


#include 
#define p 1000000007
struct matrix{
	long long m[101][101];
};
typedef struct matrix Matrix;
long long n;

Matrix work(Matrix a,Matrix b)
{
	Matrix tmp;
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=n;j++)
		{
			tmp.m[i][j]=0;
			for (long long k=1;k<=n;k++)
				tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j])%p;
		}
	return tmp;
}

Matrix ksm(Matrix a,long long m)
{
	Matrix tmp=a,b=a;
	m--;
	while (m>0)
	{
		if (m%2==1) tmp=work(b,tmp);
		b=work(b,b);
		m=m/2;
	}
	return tmp;
}

int main()
{
	long long k;
	Matrix a;
	scanf("%lld%lld",&n,&k);
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=n;j++) scanf("%lld",&a.m[i][j]);
	a=ksm(a,k);
	for (long long i=1;i<=n;i++)
	{
		for (long long j=1;j<=n;j++)
			printf("%lld ",a.m[i][j]);
		printf("\n");
	}
	return 0;
}

===comment=== 一道模板题。矩阵快速幂的运用范围还是挺广的。 ==== 冯宇扬 ==== 就[[2020-2021:teams:no_morning_training:fayuanyu:cf_r660d2|cf 660 div 2]]吧 ==== 常程 ==== 本周摸了