HDU 1757,1575,2604,2256 矩阵快速幂总结

2024-06-08 23:48
文章标签 总结 快速 矩阵 hdu 1575 2604 1757 2256

本文主要是介绍HDU 1757,1575,2604,2256 矩阵快速幂总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 1757:

就是由f(x)可以得出矩阵……可以得到下面的a0到a9并上有1，0的矩阵，与f0到f9相乘一次可以得到f1到f10，所以^(k-9)次就可以得到fn-9到fn了，第一行就是f(k)……


这个图来自：http://www.cnblogs.com/wally/archive/2013/03/01/2938305.html

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define MN 3005
//#define INF 1000000007
#define eps 1e-7
using namespace std;
typedef long long ll;
#define Max 10
int INF;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int m,k;while(~scanf("%d%d",&k,&m)){int i,j=9,sum=0;INF=m;Matrix res;mem(res.m,0);for(i=0;i<10;i++)scanf("%d",&res.m[0][i]);if(k<10) {pri(k%m);continue;}for(i=1;i<10;i++)res.m[i][i-1]=1;res=quickpow(res,k-9);for(i=0;i<10;i++)sum=(sum+res.m[0][i]*(j--))%m;pri(sum);}return 0;
}

HDU 1575：

先求幂后再求主对角线的和。

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 10
#define INF 9973
#define eps 1e-7
using namespace std;
typedef long long ll;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int t;sca(t);while(t--){int i,n,k,j=9,sum=0;scanf("%d%d",&n,&k);Matrix res;mem(res.m,0);for(i=0;i<n;i++)for(j=0;j<n;j++)sca(res.m[i][j]);res=quickpow(res,k);for(i=0;i<n;i++)sum=(sum+res.m[i][i])%INF;pri(sum);}return 0;
}

HDU 2604

分析;

解法一：同L=2时的状态递推出后面的状态：

其4个状态，分别是：fm,ff,mm,mf。

fm只可以到mm（因为fmf不符和要求了）

ff只可以到fm（同理）

mm可以到mm，mf

mf可以到fm，ff

所以构造的矩阵是

        fm   ff   mm  mf

fm     0     0    1      0

ff       1     0    0      0

mm   0    0     1      1

mf     1    1     0      0


解法二：同L=0到L=5值递推出来：

1 根据题目的意思，我们可以求出F[0] = 0 , F[1] = 2 , F[2] = 4 , F[3] = 6 , F[4] = 9 , F[5] = 15

2 那么根据上面前5项我们可以求出n >= 5的时候 F[n] = F[n-1]+F[n-3]+F[n-4]

    那么我们就可以构造出矩阵

    | 1 0 1 1 |     | F[n-1] |    | F[n] |

    | 1 0 0 0 |  *  | F[n-2] | = | F[n-1] |

    | 0 1 0 0 |     | F[n-3] |    | F[n-2] |

    | 0 0 1 0 |     | F[n-4] |    | F[n-3] |

设上面构造矩阵为a，则为a^(l-4)*f[4]=f[l-4]. 

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 4
//#define INF 9973
#define eps 1e-7
using namespace std;
typedef long long ll;
int INF;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int i,j,k,n;int a[6]={0,2,4,6,9,15},b[5]={9,6,4,2};while(~scanf("%d%d",&k,&n)){if(k<5) {pri(a[k]%n);continue;}Matrix res;mem(res.m,0);int sum=0;INF=n;res.m[0][0]=res.m[0][3]=res.m[0][2]=1;res.m[1][0]=res.m[2][1]=res.m[3][2]=1;res=quickpow(res,k-4);for(i=0;i<Max;i++)sum=(sum+res.m[0][i]*b[i])%INF; //乘以前一个1到4的矩阵pri(sum);}return 0;
}


HDU 2256

这题确实不是自己能会的题了，而且是看了别人的解题报告看了好久才明天啥意思……唉……数学退化太快了……

分析网址：http://blog.csdn.net/chenguolinblog/article/details/10212567

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 2
#define INF 1024
#define eps 1e-7
using namespace std;
typedef long long ll;
//int INF;
struct Matrix //快速幂模板
{int m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,int n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
};
int main()
{int t,n,sum;sca(t);while(t--){sca(n);if(n==1) {pri(9);continue;}Matrix res;mem(res.m,0);res.m[0][0]=5,res.m[0][1]=12;res.m[1][0]=2,res.m[1][1]=5;res=quickpow(res,n-1);sum=(res.m[0][0]*5+res.m[0][1]*2)%INF;sum=(2*sum-1)%INF;pri(sum);}return 0;
}



这篇关于HDU 1757,1575,2604,2256 矩阵快速幂总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1043659。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
hdu 3790 (单源最短路dijkstra）

hdu 3790 (单源最短路dijkstra）

题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2