2019清明期间qbxt培训qaq
4.4下午：矩阵qwq
- part1矩阵乘法：
- 概念：
一个m×p的矩阵A 乘 一个p×n的矩阵B 得到一个矩阵一个m×n的矩阵AB
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。其中：
矩阵乘法满足结合律、分配率，不满足交换律
矩阵乘法—solution：
struct m{ int a[2][2]; }; m operator *(m a,m b){ m c; for(int i=0;i<=1;i++) for(int j=0;j<=1;j++){ c.a[i][j]=0; for(int k=0;k<=1;k++) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p; }return c;}
eg1：斐波那契数列
【题目背景】
yy最近在数学课上学了斐波那契数列，已知斐波那契数列满足f（n）=f（n-1）+f（n-2）且f(1)=f(2)=1，现在yy的老师想要考考他们，老师随意给出一个数k，要大家一个个的回答他斐波那契数列的第k项，下一个就轮到yy了，但 yy做了半天，怎么也想不到做法，请你写一个程序帮助yy快速的算出第k项。
【输入格式】
输入只有一行，为这个数k。
【输出格式】
只有一行，输出斐波那契数列的第k项（取模1e9+7）
【输入样例】 【输出样例】
15 610
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long p=1000000007; int k; struct m{ int a[2][2]; }; m operator *(m a,m b)//矩阵乘法的标程qwq { m c; for(int i=0;i<=1;i++) for(int j=0;j<=1;j++){ c.a[i][j]=0;//先把全部的值都赋为0 for(int k=0;k<=1;k++) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
//eg： 1.c.a[0][0]=(c.a[0][0]+a.a[0][0]*b.a[0][0])%pp;
// 2.c.a[0][0]=(c.a[0][0]+a.a[0][1]*b.a[1][0])%pp;
//综上：c.a[0][0]=(a.a[0][1]*b.a[1][0]+a.a[0][0]*b.a[0][0])%pp;
} return c; } int main() { cin>>k; m a; a.a[0][0]=0;a.a[1][0]=1; a.a[0][1]=1;a.a[1][1]=1; m ans; ans.a[0][0]=1;ans.a[1][0]=0; ans.a[0][1]=0;ans.a[1][1]=1;//单位矩阵，当一来用； int b=k-1; while(b){//结构体乘法 利用快速幂思想 if(b&1)ans=ans*a; a=a*a; b/=2; } int fk=(ans.a[0][1]+ans.a[0][0])%p;//ans.a[0][0]*f(1)+ ans.a[0][1]*f(2) cout<<fk<<endl; }
思路：构建转移矩阵：
eg2：
【题目背景】
yy今天又上数学课了，这次老师又问了yy一个新问题：
计算f(n) = 4f(n-1) – 3f(n-2) + 2f(n-4) 的第k项，老师会给定这个数列的前四项，以及一个数k，老师说如果yy可以解出来就以yy的名字命名这个数列，yy很想有一个以他名字命名的数列，请你帮帮他。
【输入格式】
第一行：四个数，分别为这个数列的第1,2,3,4项；
第二行：一个数k表示要求的是这个数列的第几项。
【输出格式】
一个数，为这个数列的第k项
【输入样例】 【输出样例】
1 1 3 5 3711（不对请指正）
10
struct along{ int a[4][4]; }; along operator *(along a,along b) { along c; for(int i=0;i<=3;i++){ for(int j=0;j<=3;j++){ c.a[i][j]=0; for(int k=0;k<=3;k++) c.a [i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p; } } return c; } int main() { int x,y,z,w,k; cin>>x>>y>>z>>w; cin>>k; int b=k-1; along a; a.a[0][0]=0;a.a[1][0]=1;a.a[2][0]=0;a.a[3][0]=0; a.a[0][1]=0;a.a[1][1]=0;a.a[2][1]=1;a.a[3][1]=0; a.a[0][2]=0;a.a[1][2]=0;a.a[2][2]=0;a.a[3][2]=1; a.a[0][3]=2;a.a[1][3]=0;a.a[2][3]=-3;a.a[3][3]=4;//转移矩阵 along ans; ans.a[0][0]=1;ans.a[1][0]=0;ans.a[2][0]=0;ans.a[3][0]=0; ans.a[0][1]=0;ans.a[1][1]=1;ans.a[2][1]=0;ans.a[3][1]=0; ans.a[0][2]=0;ans.a[1][2]=0;ans.a[2][2]=1;ans.a[3][2]=0; ans.a[0][3]=0;ans.a[1][3]=0;ans.a[2][3]=0;ans.a[3][3]=1;//单位矩阵 while(b){ if(b&1)ans=ans*a; a=a*a; b/=2; } int fk=(ans.a[0][0]*x+ans.a[1][0]*y+ans.a[2][0]*z+ans.a[3][0]*w)%p; cout<<fk<<endl; }//include什么的自己加吧qwq
（为什么我u盘老是丢东西啊啊啊恐惧哪天培训的东西丢光了（Dev一改代码就丢啊啊啊）自闭）
我滴思路？？
1.自己搞一搞，搞出转移矩阵(至于怎么搞，可以参见eg1
ps：之前一直搞不懂的一点，就是这个奇奇怪怪的式子乘转移矩阵的k-1次方是怎么搞到的fk，后来发现fk就是那个奇奇怪怪的式子啊qwq（大概没讲明白）
2.写代码(打表一时爽)
eg3：（poj3233）
【题目背景】
yy看中了nili千古神犇zay的一包金色袋子的零食，yy决定为难一下zay，于是yy问了azy一道题：给定一个n*n的矩阵A，求A + A^2 + A^3 + … + A^k的结果。zay居然不会qwq！显然zay不能在yy面前chuchou，现在请你帮帮zay，使他快速的算出来，如果算不出来，zay的零食就是yy的了qwq
- part2高斯消元 ：
原理不想讲辽，gc数学都说了，直接理解代码吧……
【题目背景】
某腾讯游戏最近新出了高斯消消乐，大佬wz想要去腾讯游戏应聘，现在公司要求写高斯消元的代码，请你帮帮他，帮他写一份代码吧qwq
【输入格式】
第一行：两个数，分别为m和n（其实他俩一样的qwq）
第2~m+1行：每行n+1个数，分别表示n个数和一个答案
【输出格式】
输出消元后的矩阵
【输入样例】 【输出样例】
没有输入样例 没有输出样例
只有求助解释check
上代码（from lh）（注释from lz）：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pr; const double pi=acos(-1); #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Rep(i,u) for(int i=head[u];i;i=Next[i]) #define clr(a) memset(a,0,sizeof a) #define pb push_back #define mp make_pair #define fi first #define sc second ld eps=1e-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} ll read(){ ll ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } //head（lh的代码头） int n,m; double a[100][100]; bool check(int k){ if(fabs(a[k][n+1])<eps)return 1;// 如果小于0，返回1 for(int i=1;i<=n;i++) if(fabs(a[k][i])>eps)return 1;//第k行的每个数都大于0 return 0; } int main(){ n=read();m=read();//m*n的矩阵， // a_i,1 a_i,2 ... a_i,n a_i,n+1 for(int i=1;i<=m;i++) for(int j=1;j<=n+1;j++)a[i][j]=read();//输入矩阵元素(因为除了这个m*n的矩阵，还要有一行答案qwq） （看洛谷题吧qwq） for(int j=1;j<=m;j++){ for(int k=1;k<=n+1;k++)cout<<a[j][k]<<" "; puts(""); }//先把矩阵输出辽一遍 int flag=0; for(int i=1;i<=n;i++){ int t=i; while(a[t][i]==0 && t<=n)t+=1; if(t==n+1){ flag=1; continue; }//if判断是否有一行全为0，如果全为0 那么我们就少了至少1个方程，那么这个方程显然无唯一解 for(int j=1;j<=n+1;j++)swap(a[i][j],a[t][j]);//交换第i行和第t行的值，目的在于交换第i行和第t行后可以使a[1][1]！=0 double kk=a[i][i];//找到对角线qwq for(int j=1;j<=n+1;j++)a[i][j]/=kk;//把这一行的每一项都除以对角线，使得对角线为1 for(int j=1;j<=m;j++) //这里真的要详细地讲一讲咯 if(i!=j){//首先i！=j这样就不再消对角线上的数了 double kk=a[j][i];//定义kk为第j行第i列的数 for(int k=1;k<=n+1;k++)//把每一项消成0qwq（先把第一列除了对角线全消为0然后第二第三……） // 关于处理对角线这里以i=1，j=3做例子：当k=3时，a[3][3]-=a[3][1]*a[1][3]而这个时候a[3][1]已经为0，故对对角线无影响 a[j][k]-=kk*a[i][k]; } puts("------------");//画一个杠杠来分割每一次消元结果 for(int j=1;j<=m;j++){ for(int k=1;k<=n+1;k++)cout<<a[j][k]<<" ";//输出每次消元结果 puts("");//输出空格 } } if(flag){//判断无解和多解的情况（上面已经提到了） 已经懵bi求救qwq for(int i=1;i<=m;i++) if(!check(i)){//利用check判断是无解还是多解 printf("No solution\n"); return 0; } //每个答案行如果有一个等于0的数就多解？？ printf("So many solutions\n"); } }
