题目描述
婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的行
列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用
来表示矩阵中第
行第
列的元素,则
满足下面的递推式:
递推式中都是给定的常数。
现在婷婷想知道的值是多少,请你帮助她。
由于最终结果可能很大,你只需要输出除以
的余数。
输入格式
一行有六个整数。意义如题所述。
输出格式
包含一个整数,表示除以
的余数。
题目解析
考虑若知道,怎样
求出
。
根据前一个递推式,有
根据后一个递推式,有
观察上述递推式,可以发现唯一有些麻烦的是。可以用等比数列求和公式,也可以矩阵快速幂。我采用矩阵快速幂
求。设
,则有
,
矩阵快速幂即可求得
,再通过上述递推式即可求得
。
时间复杂度。
值得注意的是,本题中因为指数较大,转成二进制复杂度太高。可以直接用十进制快速幂解决。具体思想和二进制快速幂是一样的,常数略大,需要适当优化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
/************************************************************** Problem: 3240 User: frank_c1 Language: C++ Result: Accepted Time:11352 ms Memory:10068 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=(int)(1e6)+5; const int mo=(int)(1e9)+7; struct Matrix { int r,c; LL mat[3][3]; Matrix(int a=0,int b=0):r(a),c(b) { mat[1][1]=mat[1][2]=mat[2][1]=mat[2][2]=0; } } A,G,T[5],K[10]; Matrix operator * (Matrix a,Matrix b) { Matrix c(a.r,b.c); REP(k,1,a.c) REP(i,1,a.r) REP(j,1,b.c) c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mo; return c; } Matrix MatPow(Matrix a,int p[]) { Matrix c(a.r,a.c); if(p[1]<0) return c; REP(i,1,a.r) REP(j,1,a.c) c.mat[i][j]=(i==j); K[0]=c;REP(i,1,9) K[i]=K[i-1]*a; REP(i,1,p[0]) { T[0]=c; REP(k,1,3) T[k]=T[k-1]*T[k-1]; c=T[3]*T[1]*K[p[i]]; } return c; } int n[maxn],m[maxn]; char num[maxn]; inline void input(int a[]) { scanf("%s",num+1); a[0]=strlen(num+1); REP(i,1,a[0]) a[i]=num[i]-'0'; } inline void dec(int a[]) { a[a[0]]--; PER(i,a[0],2) if(a[i]<0) a[i]+=10,a[i-1]--; if(a[0]>1 && a[1]<=0) { REP(i,1,a[0]-1) a[i]=a[i+1]; a[0]--; } } int main() { input(n);input(m); dec(n);dec(m);dec(m); LL a,b,c,d; read(a);read(b);read(c);read(d); A.r=A.c=G.r=G.c=2; A.mat[1][2]=A.mat[2][2]=a;A.mat[1][1]=1;A.mat[2][1]=0; G.mat[1][1]=G.mat[2][1]=1; G=MatPow(A,m)*G; a=G.mat[2][1]*a%mo;b=b*G.mat[1][1]%mo; A.mat[1][1]=a*c%mo;A.mat[1][2]=A.mat[2][2]=1;A.mat[2][1]=0; G.mat[1][1]=1;G.mat[2][1]=(b*c+d)%mo; G=MatPow(A,n)*G; printf("%lld\n",(G.mat[1][1]*a+b)%mo); return 0; } |