近期学的一些小知识

近期学了一些比较简单的东西，就不单独开个blog了

1、Floyd 求 最小环

我觉得学了这个真的很加深对 $floyd$floyd 的理解啊。由于我们每次枚举到的中间点 $k$k 都不参与前面 $i-j$i−j 的最短路中，所以我们可以以 $k$k 和 相邻的两个点 $i,j$i,j 构成一个环。

代码如下

for(k = 1; k <= n; k++){
		for(i = 1; i <= n; i++){
			for(j = 1; j <= n; j++){
				if(i == j || i == k || k == j) continue;
				ans = min(ans, f[i][j] + mp[i][k] + mp[k][j]);

			}
		}
		for(i = 1; i <= n; i++)
			for(j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	}

2、矩阵快速幂

原理和快速幂一样，只是把乘法变成了矩阵乘法。由于函数无法返回一个数组，所以我们用结构体把矩阵封装起来。

代码如下

#include <bits/stdc++.h>
#define LL long long
#define mod 1000000007
#define mem(p) memset(&p, 0, sizeof(p))
using namespace std;
LL z = 1;
struct mat{
	LL a[105][105];
	int r, c;
};
mat p, ans;
int n;
mat matmul(mat x, mat y){
	int i, j, k;
	mat p;
	mem(p);
	for(i = 0; i < x.r; i++){
		for(j = 0; j < y.c; j++){
			for(k = 0; k < x.c; k++){
				p.a[i][j] = (p.a[i][j] + z * x.a[i][k] * y.a[k][j] % mod) % mod;
			}
		}
	}
	p.r = x.r; p.c = y.c;
	return p;
}
void mul(LL b){

	int i, j;

	while(b){

		if(b & 1) ans = matmul(ans, p);
		p = matmul(p, p);
		b >>= 1;
	}
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++) printf("%d ", ans.a[i][j]);
		printf("\n");
	}
}
int main(){
	int i, j, c;
	LL k;
	scanf("%d%lld", &n, &k);
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++){
			scanf("%d", &c);
			p.a[i][j]  = ans.a[i][j] = c;
		}
	p.r = ans.r = p.c = ans.c = n;
	mul(k - 1);
	return 0;
}