首页 > 其他 > 详细

矩阵专题(续)

时间：2016-07-08 11:53:19      阅读：283      评论：0      收藏：0      [点我收藏+]

哈哈哈，失踪人员回归。最近总是在忙一些乱七八糟的事情，终于有了一段空闲时间可以刷刷题了。学姐给我准备了kuangbin先生的矩阵专题，作为我的矩阵终结专题。（初学者请先看我的矩阵专题前三篇）


第一题 CodeForces 450B

分析：这道题看似是一道矩阵题，但是实际上是一道模拟题。看题目给出的公式 f(i)=f(i-1)+f(i+1),i>=2，那么转换一下得到了f(i)=f(i-1)-f(i-2),i>=3，当然这题可以使用矩阵快速幂来算，但是多此一举。不妨将f(1)=x  f(2)=y代进去计算前几项，那么依次得到 x   y   y-x   -x   -y   x-y   x   y   ......，我们发现这个数列是有循环节的，而且必定为6，那么只需要计算前六个，n取一下模即可得到答案。注意：x  y可能是负数，但是答案一定得是非负整数。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          200000+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

ll dat[10];
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	ll n;
	scanf("%I64d %I64d",&dat[1],&dat[2]);
	dat[1]=(dat[1]+mod)%mod;
	dat[2]=(dat[2]+mod)%mod;
	scanf("%I64d",&n);
	dat[0]=(dat[1]-dat[2]+mod)%mod;
	for(int i=3;i<6;i++)
		dat[i]=(dat[i-1]-dat[i-2]+mod)%mod;
	printf("%I64d\n",dat[n%6]);
    return 0;
}



第二题  HDU 5015

题目大意：给你一个矩阵，矩阵第一行中，第一个数为空，之后的数就是233，2333，23333。。。一直轮下去。然后，矩阵第一列上，第一个数为空（即第一行第一列的那个数为空），之后的所有数会给出。接着，告诉你这个矩阵其他元素都是按照maze[i][j]=maze[i-1][j]+maze[i][j-1]的规律来计算的，让你求出矩阵右下角的数是多少。

分析：一开始没有往矩阵方面想，前段时间数论做多了之后很容易就发现最后的maze[n][m]的数可以通过已知的数乘一个数（满足一个组合数，杨辉三角），然后相加得到。虽然我公式推出来了，但是复杂度太高，而且写起来还麻烦，就被我pass了，有兴趣的朋友可以自己推一推写一写。然后回过去想矩阵做法的话，立刻就想到了（提示n的值很大，但是m的值不大）。将输入的23(第一个23是补充上去的，为了和之后的23333对齐),maze[1][0],maze[2][0],maze[3][0],......作为初始值，根据公式很容易看出转换的矩阵，除了第一个233是前一个23乘10加3，其他的都是maze[i][j]=maze[i-1][j]+maze[i][j-1]。

技术分享

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          10+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

ll mul(ll a,ll b){
	ll ans=0;
	while(b){
		if(b&1)ans=(ans+a)%mod;
		a=(a+a)%mod;
		b>>=1;
	}
	return ans;
}
struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%10000007;
		return ans;
	}
};
matrix qlow(matrix a,int n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int n,m;
	while(~scanf("%d %d",&n,&m)){
		matrix ans;
		ans.init(n+2);
		for(int i=1;i<=n;i++)
			scanf("%lld",&ans.maze[0][i]);
		ans.maze[0][0]=23;
		ans.maze[0][n+1]=1;
		matrix ant;
		ant.init(n+2);
		for(int i=0;i<=n;i++)
			ant.maze[0][i]=10,ant.maze[n+1][i]=3;
		ant.maze[n+1][n+1]=1;
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				ant.maze[i][j]=1;
		ant=qlow(ant,m);
		ans=ans*ant;
		printf("%lld\n",ans.maze[0][n]);
	}
    return 0;
}




第三题 HDU 4990
分析：简单来看就是一个数列计算问题。F(0)=0.如果i为奇数，那么F(i)=2*F(i-1)+1；如果i为偶数，那么F(i)=2*F(i-1)。很显然是一道矩阵问题，我们不妨将两步合成一步来做F(i)=4*F(i-2)+2,i为偶数，那么我们按照2个2个来计算，计算到不超过n的最大偶数。最后，如果n为奇数的话，再计算一步即可。

技术分享

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn         	0+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

int m;
struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%m;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int n;
	while(~scanf("%d %d",&n,&m)){
		matrix ant;
		ant.init(2);
		ant.maze[0][0]=4;
		ant.maze[1][0]=2;
		ant.maze[1][1]=1;
		ant=qlow(ant,n/2);
		ll ans=ant.maze[1][0];
		if(n&1)ans=(ans*2+1)%m;
		cout<<ans<<endl;
	}
    return 0;
}




第四题 UVA 11651
分析：不会做，看了别人的题解才会的。这里我讲一下思路，作为纯DP题的话，转移方程很好想，但是score太大，无法记忆化搜索；但是作为纯矩阵题的话，一开始完全想不到如何构造矩阵。然后把两者合在一起想，就发现还是矩阵的套路，但是要加上DP的思想（以DP的状态为转移）。将一开始所有可能转移的数据全部算出来作为初始数据，部分数据直接移位就行了，主要就是最后一行的数据（要计算的新数据），需要用到前面所有数据来计算。

我知道读者肯定没有看懂，无妨，请转到这位大神的博客，他写得很好，这里我贴下我的代码

http://www.cnblogs.com/AOQNRMGYXLMV/p/5256508.html

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          150+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
//const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

int n,m,base,score;
unsigned int d[40][10];
struct matrix{
	int n;
	unsigned int maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]+=maze[i][k]*rhs.maze[k][j];
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
unsigned int solve(){
	scanf("%d %d",&base,&score);
	if(base==2)return 1;
	m=(base-1)*(base-1);
	n=base*m;
	for(int i=1;i<base;i++)
		d[0][i]=1;
	for(int i=1;i<m;i++)
		for(int j=0;j<base;j++){
			d[i][j]=0;
			for(int k=0;k<base;k++)
				if(k!=j&&(j-k)*(j-k)<=i){
					d[i][j]+=d[i-(j-k)*(j-k)][k];
				}
		}
	/*for(int i=0;i<m;i++){
		for(int j=0;j<base;j++)
			cout<<d[i][j]<<" ";
		cout<<endl;
	}*/
	if(score<m){
		unsigned int cnt=0;
		for(int i=0;i<base;i++)
			cnt+=d[score][i];
		return cnt;
	}
	matrix ans;
	ans.init(n);
	for(int i=0;i<m;i++)
		for(int j=0;j<base;j++)
			ans.maze[0][i*base+j]=d[i][j];
	matrix ant;
	ant.init(n);
	for(int j=0;j<(m-1)*base;j++)
		ant.maze[j+base][j]=1;
	for(int j=(m-1)*base;j<n;j++){
		int ss=m,bb=j%base;
			for(int i=0;i<base;i++)
				if(i!=bb){
					int sst=ss-(i-bb)*(i-bb);
					if(sst>=0){
						ant.maze[sst*base+i][j]=1;
					}
				}
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			cout<<ant.maze[i][j]<<" ";
		cout<<endl;
	}*/
	ant=qlow(ant,score-m+1);
	ans=ans*ant;
	unsigned int cnt=0;
	for(int i=0;i<base;i++)
		cnt+=ans.maze[0][n-1-i];
	return cnt;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++)
		printf("Case %d: %u\n",cas,solve());
    return 0;
}




第五题 HDU 4965
分析：一看完题目，没有多想就开始撸矩阵快速幂，想直接按照题意来计算。但是很可惜，连编译都没有过，一个是因为我的矩阵模版太烂了开不了n*n的矩阵，第二个是没有找对方法复杂度太高。直接按照题意来计算的话，那么就是M‘ = (A*B)^(一个数，具体什么数不用管),但是A是n*k的矩阵，B是k*n的矩阵，A*B就是n*n的矩阵，不是很好计算。那么我们就想到了线性代数的一个方法，将它拆开来。有M‘ = A* (B*A)^(一个数，是前面那个大数减一)*B，这样的话，可以看到B*A是k*k的矩阵，而k是一个很小的数，很容易计算。 

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          0+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
//const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

struct matrix{
	int n;
	int maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%6;
		return ans;
	}
};
matrix qlow(matrix a,int n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int A[1010][10];
int B[10][1010];
int C[1010][10];
int D[1010][1010];
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int n,k;
	while(scanf("%d %d",&n,&k),n||k){
		for(int i=0;i<n;i++)
			for(int j=0;j<k;j++)
				scanf("%d",&A[i][j]);
		for(int i=0;i<k;i++)
			for(int j=0;j<n;j++)
				scanf("%d",&B[i][j]);
		matrix ans;
		ans.init(k);
		for(int i=0;i<k;i++)
			for(int j=0;j<k;j++)
				for(int h=0;h<n;h++)
					ans.maze[i][j]=(ans.maze[i][j]+B[i][h]*A[h][j])%6;
		ans=qlow(ans,n*n-1);
		for(int i=0;i<n;i++)
			for(int j=0;j<k;j++){
				C[i][j]=0;
				for(int h=0;h<k;h++)
					C[i][j]=(C[i][j]+A[i][h]*ans.maze[h][j])%6;
			}
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++){
				D[i][j]=0;
				for(int h=0;h<k;h++)
					D[i][j]=(D[i][j]+C[i][h]*B[h][j])%6;
			}
		ll ant=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				ant+=D[i][j];
		cout<<ant<<endl;
	}
    return 0;
}




第六题 UVA 11551
分析：比较水的矩阵题，题目看懂没什么大问题。a0，a1，。。。a(n-1)就是初始值，然后直接按照题目给的数据构造矩阵即可。 

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          50+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------


struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%1000;
		return ans;
	}
};
matrix qlow(matrix a,int n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int n,r;
		scanf("%d %d",&n,&r);
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			scanf("%lld",&ans.maze[0][i]);
		matrix ant;
		ant.init(n);
		for(int i=0;i<n;i++){
			int k;
			scanf("%d",&k);
			while(k--){
				int a;
				scanf("%d",&a);
				ant.maze[a][i]=1;
			}
		}
		ant=qlow(ant,r);
		ans=ans*ant;
		int cnt=0;
		for(int i=0;i<n;i++){
			if(cnt)putchar(' ');
			cnt=1;
			printf("%lld",ans.maze[0][i]);
		}
		puts("");
	}
    return 0;
}




第七题 UVA 10689
分析：很简单的一道矩阵题，比较常规。直接按照斐波那契数列的矩阵构造方法即可，没有任何坑点。 

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          0+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------


ll m;
struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%m;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		ll a,b,n;
		scanf("%lld %lld %lld %lld",&a,&b,&n,&m);
		if(n==0){
			printf("%lld\n",a);
			continue;
		}
		if(m==1)m=10;
		else if(m==2)m=100;
		else if(m==3)m=1000;
		else m=10000;
		//cout<<m<<endl;
		matrix ans;
		ans.init(2);
		ans.maze[0][1]=ans.maze[1][0]=ans.maze[1][1]=1;
		ans=qlow(ans,n-1);
		printf("%lld\n",(a*ans.maze[0][1]+b*ans.maze[1][1])%m);
	}
    return 0;
}




第八题 UVA 11149

分析：以前在poj上做过一个几乎一模一样的，可以用二分做，也可以直接矩阵快速幂。（不明白去看一前面的矩阵专题）注意一下，结束条件。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          90+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%10;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int n;
	ll k;
	while(scanf("%d %lld",&n,&k),n){
		matrix ans;
		ans.init(n<<1);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++){
				scanf("%lld",&ans.maze[i][j]);
				ans.maze[i][j]%=10;
				ans.maze[i][j+n]=ans.maze[i][j];
			}
		for(int i=0;i<n;i++)ans.maze[i+n][i+n]=1;
		ans=qlow(ans,k);
		for(int i=0;i<n;i++){
			int cnt=0;
			for(int j=0;j<n;j++){
				if(cnt)putchar(' ');
				cnt=1;
				printf("%lld",ans.maze[i][j+n]);
			}
			puts("");
		}
		puts("");
	}
    return 0;
}




第九题 UVA 10655

分析：题目给你a+b与ab的值，让你求出a^n+b^n。题目描述很简单，解法也比较好想到。对于a^n+b^n，那么考虑a^(n-1)+b^(n-1)，两者之间的联系是a^n+b^n = [a^(n-1)+b^(n-1)] * (a + b) - ab * (a^(n-2) + b^(n-2)) , n>=2。那么可以构造矩阵

技术分享

注意：-ab要使用加分逆元变成正数！还有p=0，q=0不一定代表输入结束！（特别坑，在这个地方上耍我，出题人一定缺少关爱!）

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          0+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------


struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]+=maze[i][k]*rhs.maze[k][j];
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	ll p,q,k;
	while(scanf("%lld %lld",&p,&q)){
		if(!(~scanf("%lld",&k))){
			return 0;	
		}
		if(k==0){
			puts("2");
			continue;
		}
		matrix ans;
		ans.init(2);
		ans.maze[0][0]=2;ans.maze[0][1]=p;
		matrix ant;
		ant.init(2);
		ant.maze[1][0]=1;ant.maze[0][1]=-q;
		ant.maze[1][1]=p;
		ant=qlow(ant,k-1);
		ans=ans*ant;
		cout<<ans.maze[0][1]<<endl;
	}
    return 0;
}




第十题 UVA 1386
分析：题目不是很难，而且矩阵很快就可以构造出来

技术分享

但是呢，有个小问题，这个矩阵太大了，n可以到500，说不定会超时（我没写过，不知道是不是一定超时）。然后这里需要用到同构矩阵优化，用一维数组模拟二维矩阵乘法。（写这道题的时候，脑子特别不清醒，想了好久才把对应关系找到，汗）不知道的可以看我前面的矩阵专题！

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          500+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
//const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

ll m;
struct matrix{
	int n;
	ll maze[maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				ans.maze[i]=(ans.maze[i]+maze[(i+n-j)%n]*rhs.maze[j])%m;
		return ans;
	}
};
matrix qlow(matrix a,int n){
	matrix ans;
	ans.init(a.n);
	ans.maze[0]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
ll dat[maxn];
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int n,d,k;
	while(~scanf("%d %lld %d %d",&n,&m,&d,&k)){
		for(int i=0;i<n;i++)
			scanf("%lld",&dat[i]);
		matrix ans;
		ans.init(n);
		ans.maze[0]=1;
		for(int i=1;i<=d;i++)
			ans.maze[i]=ans.maze[n-i]=1;
		ans=qlow(ans,k);
		/*for(int i=0;i<n;i++)
			cout<<ans.maze[i]<<" ";
		cout<<endl;*/
		int cnt=0;
		for(int i=0;i<n;i++){
			if(cnt)putchar(' ');
			cnt=1;
			ll ant=0;
			for(int j=0;j<n;j++)
				ant=(ant+dat[j]*ans.maze[(j+n-i)%n])%m;
			printf("%lld",ant);
		}
		puts("");
	}
    return 0;
}




第十一题 UVA 11885
分析：说实话，我感觉题目有点扯淡，而且答案和网上搜到的题解更加扯淡。直接上我google到的结论把，给一个n，如果n为奇数或者n小于8，那么答案是0；否则答案为 （第n-4个斐波那契数  -   n/2   +   1 ）。可能有大神能够推出这个结论把  =。= 

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          0+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
//const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

const ll mm = 987654321ll;
struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%mm;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int p;
	while(scanf("%d",&p),p){
		if((p&1)||p<8){
			puts("0");
			continue;
		}
		matrix ans;
		ans.init(2);
		ans.maze[0][0]=ans.maze[1][0]=ans.maze[0][1]=1;
		ans=qlow(ans,p-4);
		printf("%lld\n",(ans.maze[0][0]-p/2+1+mm)%mm);
	}
    return 0;
}




第十二题 CodeForces 392C
分析：这道题目，看似很难不好算，但是没有离开矩阵的核心。先求递推式，然后构造矩阵，最后代码。

技术分享

技术分享

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          80+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------


struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%mod;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	ll n;
	int k;
	scanf("%I64d %d",&n,&k);
	if(n==1){
		puts("1");
		return 0;
	}
	matrix ans;
	ans.init(2*(k+1)+1);
	for(int i=0;i<k+1;i++)
		ans.maze[0][i]=1;
	for(int i=k+1;i<2*(k+1);i++)
		ans.maze[0][i]=(ans.maze[0][i-1]<<1)%mod;
	ans.maze[0][2*(k+1)]=ans.maze[0][2*(k+1)-1]+1;
	//for(int i=0;i<=2*(k+1);i++)
	//	cout<<ans.maze[0][i]<<endl;
	matrix ant;
	ant.init(2*(k+1)+1);
	for(int i=0;i<k+1;i++)
		ant.maze[i+k+1][i]=1;
	ant.maze[k+1][k+1]=1;
	for(int j=1;j<k+1;j++)
		for(int i=0;i<=j;i++)
			ant.maze[i+k+1][j+k+1]=(ant.maze[k+1+i][k+j]+ant.maze[i+k][j+k])%mod;
	for(int j=0;j<k+1;j++)
		for(int i=0;i<=j;i++)
			ant.maze[i][j+k+1]=ant.maze[i+k+1][j+k+1]*(1ll<<(j-i))%mod;
	for(int i=0;i<2*(k+1);i++)
		ant.maze[i][2*(k+1)]=ant.maze[i][2*(k+1)-1];
	ant.maze[2*(k+1)][2*(k+1)]=1;
	//for(int i=0;i<=2*(k+1);i++){
	//	for(int j=0;j<=2*(k+1);j++)
	//		cout<<ant.maze[i][j]<<" ";
	//	cout<<endl;
	//}
	ant=qlow(ant,n-2);
	ans=ans*ant;
	printf("%I64d\n",ans.maze[0][2*(k+1)]);
    return 0;
}




第十三题 CodeForces 385E

分析：这道就是题目难懂，解法上是一道常规的矩阵题。（题目意思太麻烦了，自己百度把）

技术分享

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          0+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------

ll x;
struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator *(const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%x;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	ll sx,sy,dx,dy,t;
	scanf("%I64d %I64d %I64d %I64d %I64d %I64d",&x,&sx,&sy,&dx,&dy,&t);
	matrix ans;
	ans.init(6);
	ans.maze[0][0]=ans.maze[0][1]=ans.maze[1][1]=1;
	ans.maze[1][2]=ans.maze[1][3]=ans.maze[1][4]=1;
	ans.maze[1][5]=ans.maze[2][4]=ans.maze[2][5]=ans.maze[2][3]=1;
	ans.maze[3][2]=ans.maze[3][4]=ans.maze[3][5]=1;
	ans.maze[4][2]=ans.maze[4][4]=ans.maze[5][3]=ans.maze[5][5]=1;
	ans.maze[0][2]=ans.maze[0][3]=ans.maze[0][4]=2;
	ans.maze[2][2]=ans.maze[3][3]=ans.maze[0][5]=2;
	ans=qlow(ans,t);
	matrix ant;
	ant.init(6);
	ant.maze[0][0]=1;ant.maze[0][2]=sx-1;ant.maze[0][3]=sy-1;
	ant.maze[0][4]=(dx%x+x)%x;ant.maze[0][5]=(dy%x+x)%x;
	ant=ant*ans;
	printf("%I64d %I64d\n",ant.maze[0][2]+1,ant.maze[0][3]+1);
    return 0;
}




第十四题 FZU 1911
分析：是一道非常有意思的矩阵题。首先求前n个斐波那契数的和，比较好求，利用矩阵轻松求解。然后，后面的矩阵构造的话，尝试性的构造几个，可以得出规律：只有非零偶数可以构造出这种矩阵，而且该矩阵第一行全为1；然后抛开第一行和第一列不看，就看n*n矩阵右下角那个(n-1)*(n-1)的子矩阵，这个子矩阵的主对角线和主对角线上半个三角形全填上-1；在第二行第一列填上0；在倒数(n-2)/2个行上，对于每一行最左边的一个-1的左边一格填上0；然后其他空白地方都填上1。

技术分享
我的代码Visual C++可以过，但是 GNU C++过不了，实在搞不清楚为什么，迷！

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          0+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------


ll m;
struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator *(const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%m;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	int t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++){
		ll n;
		int anw;
		scanf("%lld %lld",&n,&m);
		matrix ans;
		ans.init(3);
		ans.maze[0][0]=ans.maze[0][1]=1;
		ans.maze[0][2]=2;
		matrix ant;
		ant.init(3);
		ant.maze[0][1]=ant.maze[0][2]=ant.maze[1][0]=1;
		ant.maze[1][1]=ant.maze[1][2]=ant.maze[2][2]=1;
		ant=qlow(ant,n-2);
		ans=ans*ant;
		anw=ans.maze[0][2];
		printf("Case %d: ",cas);
		if(anw==0||anw%2){
			puts("No");
		}
		else {
			puts("Yes");
			int cnt=0;
			for(int i=0;i<anw;i++){
				if(cnt)putchar(' ');
				cnt=1;
				putchar('1');
			}
			puts("");
			cnt=0;
			for(int i=0;i<anw;i++){
				if(cnt)putchar(' ');
				cnt=1;
				if(i==0)putchar('0');
				else printf("-1");
			}
			puts("");
			for(int i=0;i<anw-2;i++){
				cnt=0;
				if(i<(anw-2)/2){
					for(int j=0;j<anw;j++){
						if(cnt)putchar(' ');
						cnt=1;
						if(j<i+2)putchar('1');
						else printf("-1");
					}
				}
				else {
					for(int j=0;j<anw;j++){
						if(cnt)putchar(' ');
						cnt=1;
						if(j<i+1)putchar('1');
						else if(j==i+1)putchar('0');
						else printf("-1");
					}
				}
				puts("");
			}
		}
	}
    return 0;
}





第十五题 UVA 10518

分析：题目首先得看懂，不懂的自己百度把。其实就是求一个类斐波那契数列，F(1)=1，F(2)=1，F(i)=F(i-1)+F(i-2)+1，i>=3

技术分享

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define   maxn          10+10
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   clr(x,y)      memset(x,y,sizeof(x))
#define   rep(i,n)      for(int i=0;i<(n);i++)
#define   repf(i,a,b)   for(int i=(a);i<=(b);i++)
#define   pii           pair<int,int>
#define   mp            make_pair
#define   FI            first
#define   SE            second
#define   IT            iterator
#define   PB            push_back
#define   Times         10

typedef   long long     ll;
typedef   unsigned long long ull;
typedef   long double   ld;

const double eps = 1e-10;
const double  pi = acos(-1.0);
const  ll    mod = 1e9+7;
const  int   inf = 0x3f3f3f3f;

inline void RI(int& x)
{
    x=0;
    char c=getchar();
    while(!((c>='0'&&c<='9')||c=='-'))c=getchar();
    bool flag=1;
    if(c=='-')
    {
        flag=0;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(!flag)x=-x;
}

//--------------------------------------------------


ll b;
struct matrix{
	int n;
	ll maze[maxn][maxn];
	void init(int n){
		this->n=n;
		clr(maze,0);
	}
	matrix operator * (const matrix& rhs){
		matrix ans;
		ans.init(n);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
					ans.maze[i][j]=(ans.maze[i][j]+maze[i][k]*rhs.maze[k][j])%b;
		return ans;
	}
};
matrix qlow(matrix a,ll n){
	matrix ans;
	ans.init(a.n);
	for(int i=0;i<a.n;i++)ans.maze[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	//freopen("d:\\acm\\in.in","r",stdin);
	ll n;
	int cas=1;
	while(scanf("%lld %lld",&n,&b),n||b){
		matrix ans;
		ans.init(3);
		ans.maze[0][0]=ans.maze[0][2]=1;
		ans.maze[1][2]=ans.maze[2][1]=ans.maze[2][2]=1;
		printf("Case %d: %lld %lld",cas++,n,b);
		if(n==0){
			printf(" %d\n",1%b);
			continue;
		}
		matrix ant;
		ant.init(3);
		ant.maze[0][0]=ant.maze[0][1]=ant.maze[0][2]=1;
		ans=qlow(ans,n-1);
		ant=ant*ans;
		printf(" %lld\n",ant.maze[0][2]);
	}
    return 0;
}




第十六题 HDU 4549
分析：将斐波那契通项的加改成了乘，那么我们不会去记录这个数字是多少，我们发现这个数字都是有a的多少次方乘以b的多少次方决定的，那么我们记录a与b的次方数。可以简单的将乘法改写为加法，那么本质上与斐波那契的求法就没有什么区别了。

技术分享



小结： 总算完成了kuangbin先生的矩阵专题了，已经不记得这是我做完的kuangbin先生的第几个专题了！累！但是满满的充实感！




矩阵专题(续)

原文：http://blog.csdn.net/shengtao96/article/details/51849216
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！