矩阵高速幂专题(二)

久等了,第二弹来了。这次的八道题大部分都很easy。可是最后一题特别坑爹。不太好想到并且有个让人吐血的坑点。

建议以后刷Light oj的朋友们做好心理准备,那上面的题目都很坑,我曾经做过一道最小生成树。就TLE了我整整一下午,没想到这次一道矩阵高速幂又是一下午,唉~~~,心累。


第一题  zoj-3690

分析:拿到这道题,我考虑第n位的数字是什么(如果前n位都满足规则)。对于第n位的数字。考虑我能够在后面n+1位上放哪些数字。

当第n位数字小于等于k时,能够在后面放与第n位不相同的相同小于等于k的数字。有k-1种,同一时候转化为最后一位是小于等于k的情况。还能够在后面放大于k的数字。有n-k种。转化为最后一位是大于k的情况。当第n位数字大于k的情况。能够放k个小于等于k的数字,转化为最后一位小于等于k的情况。还能够放大于k的n-k个数,转化为最后一位大于k的情况。

那么我就如果,对于n个数,满足规则的且最后一位大于k的情况有A(n)种,满足情况且最后一位小于等于k的情况有B(n)种。那么就有,A(n+1)=(n-k)*A(n)+(n-k)*B(n),B(n+1)=k*A(n)+(k-1)*B(n)

注意坑点:k能够等于0,那么不适合用矩阵解(k-1<0)。 此时就是求一个整数高速幂,特判一下!

构造矩阵


<span style="font-size:18px;">#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#define maxn 0+5
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double pi = acos( -1 );
const ll mod = 1e9+7;
const double eps = 1e-10;


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;
}
ll qpow(int b,ll n)
{
	ll ans=1;
	ll a=b;
	while(n)
	{
		if(n&1)ans=ans*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans;
}
int main()
{
    //freopen("d:\acm\in.in","r",stdin);
	ll n;
	int m,k;
	while(~scanf("%lld %d %d",&n,&m,&k))
	{
		if(k==0)
		{
			printf("%lld
",qpow(m,n));
			continue;
		}
		matrix ans;
		ans.init(2);
		ans.maze[0][0]=(m-k)%mod;
		ans.maze[0][1]=k%mod;
		matrix ant;
		ant.init(2);
		ant.maze[0][0]=ant.maze[1][0]=(m-k)%mod;
		ant.maze[0][1]=k%mod;
		ant.maze[1][1]=(k-1)%mod;
		ant=qlow(ant,n-1);
		ans=ans*ant;
		printf("%lld
",(ans.maze[0][0]+ans.maze[0][1])%mod);
	}
    return 0;
}</span>




第二题 Fzu-1683

分析:没什么好分析。裸的矩阵题。

递推关系已经给你了。矩阵应该非常easy就能够构造了。所以,直接上代码!

<span style="font-size:18px;">#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#define maxn 0+5
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double pi = acos( -1 );
const ll mod = 2009;//1e9+7;
const double eps = 1e-10;


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,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 m;
	scanf("%d",&m);
	for(int cas=1;cas<=m;cas++)
	{
		int n;
		scanf("%d",&n);
		printf("Case %d: ",cas);
		if(n<=2)
		{
			if(n==0)puts("1");
			else if(n==1)puts("4");
			else puts("9");
			continue;
		}
		matrix ans;
		ans.init(4);
		ans.maze[0][0]=5;
		ans.maze[0][1]=3;
		ans.maze[0][2]=1;
		ans.maze[0][3]=9;
		matrix ant;
		ant.init(4);
		ant.maze[0][0]=ant.maze[0][3]=3;
		ant.maze[1][0]=ant.maze[1][3]=2;
		ant.maze[2][0]=ant.maze[2][3]=7;
		ant.maze[0][1]=ant.maze[1][2]=ant.maze[3][3]=1;
		ant=qlow(ant,n-2);
		ans=ans*ant;
		printf("%lld
",ans.maze[0][3]);
	}
    return 0;
}</span>




第三题 hdu-3306

分析:直接考虑S(n+1)和S(n)的关系,非常快发现S(n+1)=S(n)+A(n+1)^2。再考虑A(n+1)^2的递推,联系题目给出的式子,能够将A(n+1)拆掉,得到A(n+1)^2=[X*A(n)+Y*A(n-1)]^2。

展开得到。A(n+1)^2=X^2*A(n)^2+Y^2*A(n-1)^2+2*X*Y*A(n)*A(n-1)。

然后。发现A(n)^2和A(n-1)^2都能够放在矩阵里。可是A(n)*A(n-1)要放在矩阵里面须要考虑递推,A(n+1)*A(n)=[X*A(n)+Y*A(n-1)]*A(n)=X*A(n)^2+Y*A(n)*A(n-1)

构造矩阵


<span style="font-size:18px;">#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#define maxn 0+5
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double pi = acos( -1 );
const ll mod = 10007;//1e9+7;
const double eps = 1e-10;


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,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);
    ll n,x,y;
    while(~scanf("%lld %lld %lld",&n,&x,&y))
    {
        matrix ans;
        ans.init(4);
        ans.maze[0][0]=ans.maze[0][1]=ans.maze[0][2]=1;
        ans.maze[0][3]=2;
        matrix ant;
        ant.init(4);
        ant.maze[0][0]=y%mod;
        ant.maze[1][0]=x%mod;
        ant.maze[0][1]=ant.maze[0][3]=2*x*y%mod;
        ant.maze[1][1]=ant.maze[1][3]=x*x%mod;
        ant.maze[2][1]=ant.maze[2][3]=y*y%mod;
        ant.maze[1][2]=ant.maze[3][3]=1;
        ant=qlow(ant,n-1);
        ans=ans*ant;
        printf("%lld
",ans.maze[0][3]);
    }
    return 0;
}</span>




第四题 Uestc-1335

分析:裸的矩阵高速幂,入门题,敲着玩玩把!

啊呀,uestc oj似乎爆炸了(可能是临时的),这题这么水,代码就不用了吧




第五题  poj-3233

分析:这道题有一种二分解法,可是这里我就不介绍了,我说下我自己的写法。

我还是把S和A分开来。S(n+1)=S(n)+A^(n+1),A^(n+1)=A^(n)*A,选择一个复合矩阵(好吧。事实上叫分块矩阵),好像光看执行时间,并不快。可是这样的做法简单啊!

构造矩阵


<span style="font-size:18px;">#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#define maxn 60+5
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double pi = acos( -1 );
const ll mod = 1e9+7;
const double eps = 1e-10;


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,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,k;
	scanf("%d %d %d",&n,&k,&m);
	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][n+j]=ans.maze[i][j];
		}
	for(int i=0;i<n;i++)
		ans.maze[i+n][i+n]=1;
	ans=qlow(ans,k);
	int flag;
	for(int i=0;i<n;i++)
	{
		flag=0;
		for(int j=0;j<n;j++)
		{
			if(flag)putchar(' ');
			flag=1;
			printf("%d",ans.maze[i][j+n]);
		}
		puts("");
	}
    return 0;
}</span>



第六题 hdu-2256

分析:和专题一里面的第四题是同一种题型,并且结果也大致同样,可是身为一个负责任的博主,还是会再写一遍的,毕竟这道题具有一般性,做完这道题这类题目就都不怕了。


<span style="font-size:18px;">#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#define maxn 0+5
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double pi = acos( -1 );
const ll mod = 1e9+7;
const double eps = 1e-10;

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,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 a,b,n;
    while(~scanf("%d %d %d %d",&a,&b,&n,&m))
    {
        matrix ans;
        ans.init(2);
        ans.maze[0][0]=a%m;
        ans.maze[0][1]=1;
        ans.maze[1][0]=b%m;
        ans.maze[1][1]=a%m;
        ans=qlow(ans,n);
        printf("%lld
",ans.maze[0][0]*2%m);
    }
    return 0;
}</span>



第七题 Uva-10870

分析:除了d是变化的以外,感觉这道题和斐波那契没什么差别。没啥好说的把。直接上图和代码。


<span style="font-size:18px;">#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#define maxn 15+5
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double pi = acos( -1 );
const ll mod = 1e9+7;
const double eps = 1e-10;

int m;
int dat[maxn];
int anw[maxn];
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 d;
	ll n;
	while(scanf("%d %lld %d",&d,&n,&m),d||n||m)
	{
		for(int i=0;i<d;i++)
			scanf("%d",&anw[i]);
		for(int i=0;i<d;i++)
			scanf("%d",&dat[i]);
		if(n<=d)
		{
			printf("%d
",dat[n-1]%m);
			continue;
		}
		matrix ans;
		ans.init(d);
		for(int i=0;i<d;i++)
			ans.maze[0][i]=dat[i];
		matrix ant;
		ant.init(d);
		for(int i=0;i<d-1;i++)
			ant.maze[i+1][i]=1;
		for(int i=0;i<d;i++)
			ant.maze[i][d-1]=anw[d-1-i];
		ant=qlow(ant,n-d);
		ans=ans*ant;
		printf("%lld
",ans.maze[0][d-1]);

	}
    return 0;
}
</span>



第八题 Light oj 1132

分析:这道比較难,我来好好分析一下。

首先,看到题目表示一脸懵逼。

可是冷静下来,先认定一个事实,K是给你的常数并且很小。不应该作为递推的量度(那么就应该是N作为递推的量度)。最好还是设S(n)=1^K+2^K+......+N^K。

那么,S(n+1)=S(n)+(N+1)^K。S(n)能够放到矩阵里面作为一项,可是(N+1)^K怎么办呢?我们考虑二项式定理!

(N+1)^K=C(K,0)*N^0+C(K,1)*N^1+C(K,2)*N^2+......+C(K,i)*N^i+......+C(K,K)*N^K

那么(N+1)^K就转化为了N^0、N^1、N^2、......、N^K,那么我们考虑不如全放到矩阵里面(反正最多仅仅有50个),递推式的话还是使用二项式定理!

注意:

1、对于50之内的组合数的话。能够用公式C(n,k)=C(n-1,k)+C(n-1,k-1)打表打出来

2、这里有个大坑点,假设你直接用矩阵连着乘n次的话。中间数据就会爆long long,这时你须要一个类似高速幂的乘法,可是你真的这么写的话会超时,我看了别人的代码,才知道人家都是仅仅算n-1次(奇迹的不会爆掉,卡的真好)。然后最后一次是自己在外面写的。真是TM机智。同一时候我还要问候一下出题人的女性亲友。为什么不关爱一下出题人,让他有机会出这么反人类的题目。(当然也可能是我蠢,矩阵高速幂的姿势不好把,可是讲道理我已经优化了一下午了)

3、最大的坑点就是我的亲学长给我的矩阵高速幂模版很的烂(听说他们私下里称这个模版为傻逼TLE矩阵高速幂模版。已经在多道题目上TLE了)。然后我就崩溃了,在网上找到大神的模版后,我还不忘把他给我全部的模版通通删掉,准备有时间自己去找一波=、=。

构造矩阵


#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#define maxn 50+5
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double pi = acos( -1 );
const ll mod = (ll)1<<32;//1e9+7;
const double eps = 1e-10;
 
int siz;
ll C[maxn][maxn];
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;
}
void infi()
{
    for(int i=0;i<=50;i++)
    {
        C[i][0]=1;
        C[i][i]=1;
    }
    for(int i=2;i<=50;i++)
        for(int j=1;j<i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
struct matrix
{
    ll maze[maxn][maxn];
    matrix()
    {
        clr(maze,0);
        for(int i=0;i<siz;i++)
            maze[i][i]=1;
    }
};
matrix operator * (const matrix& A,const matrix& B)
{
    matrix ans;
    for(int i=0;i<siz;i++)
        for(int j=0;j<siz;j++)
        {
            ans.maze[i][j]=0;
            for(int k=0;k<siz;k++)
                ans.maze[i][j]=(ans.maze[i][j]+A.maze[i][k]*B.maze[k][j]%mod)%mod;
        }
    return ans;
}
matrix qlow(matrix a,ll n)
{
    matrix ans;
    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);
    infi();
    for(int cas=1;cas<=t;cas++)
    {
        ll n;
        int k;
        scanf("%lld %d",&n,&k);
        siz=k+2;
        matrix ans;
        clr(ans.maze,0);
        for(int i=0;i<=k;i++)
            for(int j=0;j<=i;j++)
                ans.maze[j][i]=C[i][j];
        for(int i=0;i<=k;i++)
            ans.maze[i][k+1]=C[k][i];
        ans.maze[k+1][k+1]=1;
        ans=qlow(ans,n-1);
        ll anw=0;
        for(int i=0;i<=k+1;i++)
            anw=(anw+ans.maze[i][k+1])%mod;
        printf("Case %d: %lld
",cas,anw);
    }
    return 0;
}




小结:刷题之余。我和同学交流了一下。才发现矩阵高速幂和DP有点像,相同是求递推、状态转移。在DP数据比較大,不能够记忆画搜索的时候,就能够使用矩阵高速幂,给出答案。

尽管没有做到这类题目,可是有种顿悟的感觉。蛮开心的!

原文地址:https://www.cnblogs.com/yjbjingcha/p/7149934.html