首页 > 其他分享 >矩阵相关模板

矩阵相关模板

时间：2023-07-15 16:13:17浏览次数：33  
标签：const int register 矩阵 while base 相关 include 模板

矩阵快速幂

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>

using namespace std;

const int N = 150;
const int mod = 1e9 + 7;
typedef long long lld;

inline int read() {
	register int w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

int n;
lld k;

struct Mat {
	int dat[N][N];
	Mat () {
		memset(dat, 0, sizeof (dat));
	}
	inline void init() {
		for (register int i = 1; i <= n; ++i)
			dat[i][i] = 1;
	}
	inline void readin() {
		for (register int i = 1; i <= n; ++i)
			for (register int j = 1; j <= n; ++j)
				dat[i][j] = read();
	}		
	inline void print() {
		for (register int i = 1; i <= n; ++i)
			for (register int j = 1; j <= n; ++j)
				printf("%d%c", dat[i][j], j == n ? '\n' : ' ');
	}
};

Mat operator * (register Mat a, register Mat b) {
	register Mat c;
	for (register int i = 1; i <= n; ++i)
		for (register int j = 1; j <= n; ++j)	
			for (register int k = 1; k <= n; ++k)
				c.dat[i][j] = (c.dat[i][j] + 1ll * a.dat[i][k] * b.dat[k][j] % mod) % mod;
	return c;
}

Mat qpow(register Mat a, register lld b) {
	register Mat base;
	base.init();
	while (b) {
		if (b & 1)  base = base * a;
		a = a * a;
		b >>= 1;
	}
	return base;
}

int main() {
	n = read();
	scanf("%lld", &k);
	register Mat a;
	a.readin();
	a = qpow(a, k);
	a.print();
	return 0;
}

矩阵加速

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5;
const int mod = 1e9 + 7;
typedef long long lld;

inline int read() {
	register int w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

struct Mat {
	int n, m;
	int dat[N][N];
	Mat () {
		memset(dat, 0, sizeof (dat));
	}
	inline void init(register int new_n, register int new_m) {
		n = new_n, m = new_m;
		for (register int i = 1; i <= n; ++i)
			dat[i][i] = 1;
	}
	inline void readin() {
		for (register int i = 1; i <= n; ++i)
			for (register int j = 1; j <= m; ++j)
				dat[i][j] = read();
	}		
	inline void print() {
		for (register int i = 1; i <= n; ++i)
			for (register int j = 1; j <= m; ++j)
				printf("%d%c", dat[i][j], j == m ? '\n' : ' ');
	}
};

Mat operator * (register Mat a, register Mat b) {
	register Mat c;
	c.n = a.n;
	c.m = a.m;
	for (register int i = 1; i <= a.n; ++i)
		for (register int j = 1; j <= b.m; ++j)	
			for (register int k = 1; k <= b.n; ++k)
				c.dat[i][j] = (c.dat[i][j] + 1ll * a.dat[i][k] * b.dat[k][j] % mod) % mod;
	return c;
}

inline Mat qpow(register Mat a, register int b) {
	register Mat base;
	base.init(a.n, a.m);
	while (b) {
		if (b & 1)  base = base * a;
		a = a * a;
		b >>= 1;
	}
	return base;
}

int n;

int main() {
	register int T = read();
	while (T--) {
		register Mat a;
		a.n = 1, a.m = 3;
		a.dat[1][1] = a.dat[1][2] = a.dat[1][3] = 1;
		register Mat base;
		base.n = base.m = 3;
		base.dat[1][1] = base.dat[1][2] = base.dat[2][3] = base.dat[3][1] = 1;
		n = read();
		n -= 3;
		if (n <= 0) {
			printf("1\n");
			continue;
		}
		base = qpow(base, n);
		a = a * base;
		printf("%d\n", a.dat[1][1]);
	}
	return 0;
}

高斯消元

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 150;
const double eps = 1e-7;
typedef long long lld;

inline int read() {
	register int w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

int n;

double a[N][N], ans[N];

int main() {
	register int T = 1;
	while (T--) {
		n = read();
		for (register int i = 1; i <= n; ++i)
			for (register int j = 1; j <= n + 1; ++j)
				scanf("%lf", &a[i][j]);
		for (register int i = 1; i <= n; ++i) {
			int r = i;
			for (register int j = r + 1; j <= n; ++j)
				if (fabs(a[r][i]) < fabs(a[j][i]))
					r = j;
			if (fabs(a[r][i]) < eps) {
				printf("No Solution\n");
				return 0;
			}
			if (r != i)  swap(a[r], a[i]);
			register double div = a[i][i];
			for (register int j = i; j <= n + 1; ++j)  a[i][j] /= div;
			for (register int j = i + 1; j <= n; ++j) {
				div = a[j][i];
				for (register int k = i; k <= n + 1; ++k)
					a[j][k] -= div * a[i][k];
			}
		}
		ans[n] = a[n][n + 1];
		for (register int i = n - 1; i >= 1; --i) {
			ans[i] = a[i][n + 1];
			for (register int j = i + 1; j <= n; ++j)
				ans[i] -= ans[j] * a[i][j];
		}
		for (register int i = 1; i <= n; ++i)
			printf("%.2lf\n", ans[i]);
	}
	return 0;
}

矩阵求逆

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 450;
const int mod = 1e9 + 7;

inline int read() {
	register int w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

int n;
int a[N][N << 1];

inline int qpow(register int a, register int b) {
	register int base = 1;
	while (b) {
		if (b & 1)  base = 1ll * base * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return base;
}

int main() {
	n = read();
	for (register int i = 1; i <= n; ++i) {
		for (register int j = 1; j <= n; ++j)	
			a[i][j] = read();
		a[i][i + n] = 1;
	}

	for (register int i = 1; i <= n; ++i) {
		register int r = i;
		for (register int j = i + 1; j <= n; ++j)
			if (a[r][i] < a[j][i])  r = j;
		if (r != i)  swap(a[r], a[i]);
		if (!a[i][i]) {
			printf("No Solution\n");
			return 0;
		}

		int div = qpow(a[i][i], mod - 2);
		for (register int k = 1; k <= n; ++k) {
			if (k == i)  continue;
			int p = 1ll * a[k][i] * div % mod;
			for (register int j = 1; j <= 2 * n; ++j)
				a[k][j] = (a[k][j] - 1ll * p * a[i][j] % mod + mod) % mod;
		}

		for (register int j = 1; j <= n * 2; ++j)
			a[i][j] = 1ll * a[i][j] * div % mod;
	}

	for (register int i = 1; i <= n; ++i)
		for (register int j = n + 1; j <= 2 * n; ++j)
			printf("%d%c", a[i][j], j == 2 * n ? '\n' : ' ');
	return 0;
}

标签：const,int,register,矩阵,while,base,相关,include,模板
From： https://www.cnblogs.com/abigjiong/p/17556282.html

相关文章

  • 模板字节转换
    #include<cstdint>#include<cstring>template<typenameT>inlineTparseData(constuint8_t*byteData,size_toffset){Tresult;std::memcpy(&result,byteData+offset,sizeof(T));returnresult;}intmain(){ui......
  • 矩阵LED分时点亮
    原理：分时驱动LED_PIN1,LED_PIN2,LED_PIN3为低电平。再来同时置位LED_SEG1,LED_SEG2,LED_SEG3,LED_SEG4,达到分时点亮矩阵LED的效果，缺点是LED比正常点亮暗一些，其他无差异。上程序voidswled(void){staticuint8_tledstep;if(ledstate&0x0080)//解决未开机亮灯......
  • Leetcode240.搜索二维矩阵II
    classSolution{public:boolsearchMatrix(vector<vector<int>>&matrix,inttarget){if(matrix.empty()||matrix[0].empty())returnfalse;intn=matrix.size(),m=matrix[0].size();intx=0,y=m-1;while(x&......
  • 线段树模板
    单点修改，区间查询给n个数a1,a2,a3,…,an。支持q个操作：1xd，修改ax=d。2lr，查询（l,r），并且求出最小值出现了多少次。输入格式第一行两个整数n,q(1≤n,q≤2×105)。接下来一行n个整数a1,a2,…,an(1≤ai≤109)。接下来q行，每行一个形如1xd或者2lr的操作，保证1≤x≤n,......
  • idea模板
    FileandCodeTemplateclass==1#if(${PACKAGE_NAME}&&${PACKAGE_NAME}!="")package${PACKAGE_NAME};#end#parse("FileHeader.java")/***<h3>${PROJECT_NAME}</h3>*<p>${description}</p>**@autho......
  • go text模板
    packageinstallimport("bytes""fmt""strings""text/template""github.com/fanux/sealos/pkg/logger""sigs.k8s.io/yaml")varConfigTypestringfuncsetKubeadmAPI(versionstring){maj......
  • 递归相关知识2
    递归相关知识2多路递归--斐波那契额数列importjava.util.Arrays;//递归求斐波那契第n项publicclassfeibonaqie{publicstaticintfibonacci(intn){int[]cache=newint[n+1];Arrays.fill(cache,-1);cache[0]=0;cache[1]=1;//......
  • 洛谷 P3372 【模板】线段树 1
    题目传送门题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某一个数加上x2.求出某区间每一个数的和输入格式第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3......
  • devicecensus.exe 是 Windows 操作系统中的一个进程，它与设备普查相关。设备普查是 Win
    devicecensus.exe是Windows操作系统中的一个进程，它与设备普查相关。设备普查是Windows操作系统收集和报告硬件和软件信息的一项功能。具体来说，devicecensus.exe是Windows的设备普查服务的主执行文件。它负责定期运行设备普查任务，收集系统的硬件配置、驱动程序信息、应用......
  • RabbitMQ相关
    1、mq安装：https://blog.csdn.net/sushipenglove/article/details/866690652、镜像集群：https://blog.51cto.com/u_15477117/4905546注意镜像集群修改主机名称后需要重新连接，才可以生效； 过程中相关命令参考：--------------------------------------------------------firew......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99