首页 > 代码库 > 【bzoj3240】 Noi2013—矩阵游戏
【bzoj3240】 Noi2013—矩阵游戏
http://www.lydsy.com/JudgeOnline/problem.php?id=3240 (题目链接)
题意
F[1][1]=1
F[i,j]=a*F[i][j-1]+b (j!=1)
F[i,1]=c*F[i-1][m]+d (i!=1)
求解F[n][m]，a，b，c，d为常数。
Solution
原来费马小定理对于矩阵乘法同样适用。。设a为一矩阵，p为质数则：
正好这里的模数1000000007为质数，那么把n,m模上(p-1)后进行矩阵快速幂即可。用来优化的矩阵很好构造，记得特判a和c等于1的情况。
注意如果重载了*，不要弄错了乘法的顺序，因为矩阵乘法是不满足交换律的。
代码
// bzoj3240#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>#define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;char s1[1000010],s2[1000010];LL n,m,a,b,c,d;struct data { LL x[3][3]; friend data operator * (const data &a,const data &b) { data tmp;tmp.x[0][1]=tmp.x[0][2]=tmp.x[0][0]=tmp.x[1][0]=tmp.x[2][0]=0; for (int i=1;i<=2;i++) for (int j=1;j<=2;j++) { tmp.x[i][j]=0; for (int k=1;k<=2;k++) tmp.x[i][j]=(tmp.x[i][j]+a.x[i][k]*b.x[k][j])%MOD; } return tmp; }}A,B,T,ans,res;void power(data a,int b) { ans.x[1][1]=1;ans.x[1][2]=0;ans.x[2][1]=0;ans.x[2][2]=1; while (b) { if (b&1) ans=a*ans; b>>=1; a=a*a; }}int main() { scanf("%s%s%lld%lld%lld%lld",s1,s2,&a,&b,&c,&d); A.x[1][1]=a;A.x[1][2]=0;A.x[2][1]=b;A.x[2][2]=1; B.x[1][1]=c;B.x[1][2]=0;B.x[2][1]=d;B.x[2][2]=1; T.x[1][1]=1;T.x[1][2]=1;T.x[2][1]=T.x[2][2]=0; LL P=MOD-1; if (a==1 && c==1) P=MOD; int l=strlen(s1); for (int i=0;i<l;i++) n=(n*10+s1[i]-‘0‘)%P; l=strlen(s2); for (int i=0;i<l;i++) m=(m*10+s2[i]-‘0‘)%P; power(A,m-1); for (int i=1;i<=2;i++) for (int j=1;j<=2;j++) A.x[i][j]=res.x[i][j]=ans.x[i][j]; A=A*B; power(A,n-1); res=ans*res; res=T*res; printf("%lld",res.x[1][1]); return 0;}
【bzoj3240】 Noi2013—矩阵游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。