首页 > 代码库 > bzoj 3240: [Noi2013]矩阵游戏 矩阵乘法+十进制快速幂+常数优化
bzoj 3240: [Noi2013]矩阵游戏 矩阵乘法+十进制快速幂+常数优化
3240: [Noi2013]矩阵游戏
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 613 Solved: 256
[Submit][Status]
Description
婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质：若用F[i][j]来表示矩阵中第i行第j列的元素，则F[i][j]满足下面的递推式:
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)
递推式中a,b,c,d都是给定的常数。
现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大，你只需要输出F[n][m]除以1,000,000,007的余数。
Input
一行有六个整数n,m,a,b,c,d。意义如题所述
Output
包含一个整数，表示F[n][m]除以1,000,000,007的余数
Sample Input
3 4 1 3 2 6
Sample Output
85
HINT
样例中的矩阵为：
1 4 7 10
26 29 32 35
76 79 82 85
本着NOIP前刷水题的想法做了这道没有数据范围的题，结果发现n,m范围实在是有一点过分了，十进制快速幂不说了，这道题应该是专门在卡普通的O(n^3)矩阵乘法，由于题目中矩阵第二行都没有变，所以说可以借此优化一下常数。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MOD 1000000007#define MAXN 2100000typedef long long qword;struct matrix{ qword a[2][2]; int n,m; matrix() { memset(a,0,sizeof(a)); } void init0() { n=m=2; a[0][0]=a[1][1]=1; a[0][1]=a[1][0]=0; } void init1(int aa,int bb) { n=m=2; a[0][0]=aa; a[0][1]=bb; a[1][1]=1; } void init2(int aa) { n=2;m=1; a[0][0]=aa; a[1][0]=1; }};inline matrix operator *(matrix m1,matrix m2){ int i,j,k; matrix ret; ret.n=m1.n; ret.m=m2.m; if (ret.n==2 && ret.m==2) { if (m1.a[1][1]!=1 || m1.a[1][0]!=0 || m2.a[1][1]!=1 || m2.a[1][0]!=0) throw 1; ret.a[0][0]=m1.a[0][0]*m2.a[0][0]%MOD; ret.a[0][1]=(m1.a[0][0]*m2.a[0][1]%MOD+m1.a[0][1])%MOD; ret.a[1][0]=0; ret.a[1][1]=1; return ret; } for (i=0;i<m1.n;i++) { for (j=0;j<m2.m;j++) { for (k=0;k<m1.m;k++) { ret.a[i][j]=(ret.a[i][j]+m1.a[i][k]*m2.a[k][j]%MOD)%MOD; } } } return ret;}matrix pow_mod(matrix a,char *str,int len){ int i,j; register matrix t,l0,ret; ret.init0(); l0.init0(); t=a; for (i=len-1;i>=0;i--) { for (j=0;j<10;j++) { if (j==str[i]-‘0‘) ret=ret*l0; l0=l0*t; } t=l0; l0.init0(); } return ret;}char s1[MAXN],s2[MAXN];int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); qword a,b,c,d,i,j,k; scanf("%s %s%lld%lld%lld%lld",s1,s2,&a,&b,&c,&d); a%=MOD;b%=MOD;c%=MOD;d%=MOD; int l1,l2; l1=strlen(s1); l2=strlen(s2); int x; x=l1-1; s1[x]--; while (s1[x]<‘0‘) { s1[x]+=10;s1[x-1]--;x--; } x=l2-1; s2[x]--; while (s2[x]<‘0‘) { s2[x]+=10;s2[x-1]--;x--; } matrix m1,r1,m2,r2,r3,m3,r4,m4; matrix t1; m1.init1(a,b); m2.init1(c,d); m4.init2(1); r1=pow_mod(m1,s2,l2); r2=m2*r1; r3=pow_mod(r2,s1,l1); r4=r1*r3*m4; cout<<r4.a[0][0]<<endl;}
bzoj 3240: [Noi2013]矩阵游戏 矩阵乘法+十进制快速幂+常数优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。