首页 > 其他分享 >P1939 矩阵加速

P1939 矩阵加速

时间:2024-09-30 21:12:31浏览次数:7  
标签:begin end int P1939 矩阵 leq bmatrix 加速

P1939 矩阵加速

已知一个数列 \(a\),它满足:

\[a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases} \]

求 \(a\) 数列的第 \(n\) 项对 \(10^9+7\) 取余的值。

  • 对于 \(100\%\) 的数据 \(1 \leq T \leq 100\),\(1 \leq n \leq 2 \times 10^9\)。

我们发现 \(n \le 2 \times 10 ^ 9\),这样我们就不能直接递推。

我们先构造答案矩阵,发现 \(a_x=a_{x - 1} + a_{x - 3}\),那么我们就需要把 \(a_x,a_{x - 1},a_{x - 2}\) 放进我们的答案矩阵。

\[\begin{bmatrix} a_x\\ a_{x - 1}\\ a_{x - 2} \end{bmatrix} \]

我们的目的是把他往前推一位,得到:

\[\begin{bmatrix} a_{x + 1}\\ a_{x}\\ a_{x - 1} \end{bmatrix} \]

行和列对应,可以得到我们的转移矩阵:

\[\begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{bmatrix} \]

那么我们只需要对开始的:

\[\begin{bmatrix} 1\\1\\1 \end{bmatrix} \]

进行 \(n - 3\) 次转移即可得到答案。

\(code\)

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
const int MAXN = 105;
const int X = 3;
int n;
struct Matrix{
	int a[MAXN][MAXN];
	void tox(){
		for(int i = 1;i <= X;i++){
			for(int j = 1;j <= X;j++){
				a[i][j] = 0;
			}
		}
	}
	void unifyInit(){
		a[1][1] = 1,a[1][2] = 0,a[1][3] = 0;
		a[2][1] = 0,a[2][2] = 1,a[2][3] = 0;
		a[3][1] = 0,a[3][2] = 0,a[3][3] = 1;
	}
	void Init(){
		a[1][1] = 1,a[1][2] = 0,a[1][3] = 1;
		a[2][1] = 1,a[2][2] = 0,a[2][3] = 0;
		a[3][1] = 0,a[3][2] = 1,a[3][3] = 0;
	}
	void print() const{
		cout<<"-------------------------\n";
		for(int i = 1;i <= X;i++){
			for(int j = 1;j <= X;j++){
				cout<<a[i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<"-------------------------\n";
	}
	Matrix operator*(const Matrix &other) const{
		Matrix ans;
		ans.tox();
		// print();
		// cout<<"***"<<endl;
		// other.print();
		for(int i = 1;i <= X;i++){
			for(int j = 1;j <= X;j++){
				for(int k = 1;k <= X;k++){
					ans.a[i][j] = (ans.a[i][j] + other.a[i][k] * a[k][j]) % MOD;
				}
			}
		}
		// cout<<"==="<<endl;
		// ans.print();
		return ans;
	}
	
};
Matrix qpow(Matrix x,int val){
	Matrix res;
	res.unifyInit();
	while(val){
		if(val & 1) res = res * x;
		x = x * x;
		val >>= 1;
	}
	return res;
}
Matrix m;
signed main(){
	int _;
	cin>>_;
	while(_--){
		int n;
		cin>>n;
		if(n == 1){
			cout<<1<<endl;
			continue;
		}else if(n == 2){
			cout<<1<<endl;
			continue;
		}else if(n == 3){
			cout<<1<<endl;
			continue;
		}
		m.Init();
		// m.print();
		m = qpow(m,n - 3);
		// m.print();
		int ans = 0;
		for(int i = 1;i <= X;i++){
			ans = (ans + m.a[1][i]) % MOD;
		}
		cout<<ans<<endl;
	}
	return 0;
}

标签:begin,end,int,P1939,矩阵,leq,bmatrix,加速
From: https://www.cnblogs.com/wyl123ly/p/18442444

相关文章

  • 手把手实现完善矩阵类(分数数据类型)
    矩阵类功能:矩阵变换分数数据类型使得精度丢失率极低加,减,数乘,矩阵相乘,转置,幂次,初等变换伴随矩阵,逆矩阵,矩阵行列式的值,后方增添/删除矩阵,矩阵的秩获取并输出齐次/非齐次线性方程组的解向量演示:矩阵输出,初等行变换后输出,解向量输出实现矩阵类,如何适应不同数据类型?模板?对......
  • 【轴承动力学】ODE45轴承故障动力学(四类)数值计算(含加速度 滚道接触力 相图)【含Matlab
    ......
  • 迅雷加速器兑换口令2024最新免费会员
    对于热爱游戏的玩家来说,网络延迟和卡顿无疑是游戏体验的致命伤。迅雷加速器以其专业和高效的服务,为全球游戏爱好者提供了解决方案。现在,新用户有机会免费领取迅雷加速器的VIP会员,享受长达7+30天的加速服务。以下是详细的领取攻略:领取7天免费会员领取7天免费会员的步骤非常简......
  • 14、图-邻接矩阵
    1、邻接矩阵的定义和初始化#include<stdio.h>#include<malloc.h>#include<assert.h>#defineDefault_Vertices_Size10//顶点#defineTchar//无向不带权的图typedefstructGraphMtx{intMaxVertices;//最大的顶点数intNumVertices;//真实的顶点数......
  • 华为OD机试2024年E卷-矩阵匹配[200分]( Java | Python3 | C++ | C语言 | JsNode | Go )
    题目描述从一个N*M(N≤M)的矩阵中选出N个数,任意两个数字不能在同一行或同一列,求选出来的N个数中第K大的数字的最小值是多少。输入描述输入矩阵要求:1≤K≤N≤M≤150输入格式:NMKN*M矩阵输出描述N*M的矩阵中可以选出M!/N!种组合数组,每个组合......
  • 算法训练营第二天| 209.长度最小的子数组、59.螺旋矩阵II
    209.长度最小的子数组状态:没写出来->确认自己的想法是对的之后写出来了!!!初始思路:因为子数组是连续的,所以可以采用滑动窗口,我把这个窗口设置为左闭右闭,所以初始左右边界为0。之后先移动右指针,使得找到第一个和大于等于target的子数组,记录其长度,之后再移动左指针一位,再找第二个......
  • leetcode74 搜索二维矩阵
    leetcode74搜索二维矩阵思路可以使用二叉搜索,首先先看标准的闭区间二叉搜索代码publicintqSearch(int[]a,intl,intr,inttarget){intmid=(l+r)/2;if(l>r)returnl;//终止条件,区间为空if(a[mid]==target)returnmid;elseif(a[mid]<target)retur......
  • 加速clone linux kernel
    tunagitclonehttps://mirrors.tuna.tsinghua.edu.cn/git/linux.gitgiteegitee.com有一个码云极速下载的用户,id是mirrors。这个用户维护了很多github的仓库的镜像,其中就有linuxkernel:[email protected]:mirrors/linux.git实测可以跑满带宽。建议不要用https的方式......
  • numpy矩阵操作
    numpy官方文档:https://numpy.org/doc/stable/pipinstallnumpyimportnumpyasnp矩阵定义$$\left[\begin{matrix}1&2\3&4\end{matrix}\right]$$a=np.array([[1,2],[3,4]])reshapehttps://numpy.org/doc/stable/reference/generated/numpy.res......
  • 代码随想录算法训练营第二天| 209.长度最小的子数组、59.螺旋矩阵II 、区间和、开发
    209.长度最小的子数组此题注重理解,同时我将res一开始初始化为sums的长度加一(因为不可能为此长度)INT32_MAX是一个常量,代表32位有符号整数的最大值classSolution{public:intminSubArrayLen(inttarget,vector<int>&nums){inti=0,j=0;//i为起始位置,j为......