Description
婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的\(n\)行\(m\)列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质：若用\(F[i][j]\)来表示矩阵中第\(i\)行>第\(j\)列的元素，则\(F[i][j]\)满足下面的递推式:
\(F[1][1]=1\)
\(F[i,j]=a \times F[i][j-1]+b (j \ne 1)\)
\(F[i,1]=c \times F[i-1][m]+d (i \ne 1)\)
递推式中\(a,b,c,d\)都是给定的常数。
现在婷婷想知道\(F[n][m]\)的值是多少,请你帮助她。由于最终结果可能很大，你只需要输出\(F[n][m]\)除以\(1000000007\)的余数。
Input
一行有六个整数\(n,m,a,b,c,d\)。意义如题所述
Output
包含一个整数，表示\(F[n][m]\)除以\(1000000007\)的余数
Sample Input
3 4 1 3 2 6
Sample Output
85
HINT
样例中的矩阵为：
\(1 \le N,M \le 10^{1000 000},1 \le a,b,c,d \le 10^9\)
首先可以肯定这题肯定是矩阵乘法。
由递推式\(F[i,j]=a \times F[i][j-1]+b (j \ne 1)\)我们可以得到这样一个矩阵乘法：
由递推式\(F[i,1]=c \times F[i-1][m]+d (i \ne 1)\)我们可以得到这样一个矩阵乘法：
但是数据范围坑爹，所以我们不能用二进制的快速幂(高精度除以\(2\)会TLE)。我们转变一下，直接使用十进制的快速幂(太神了)，这样就减少了除法的时间。
题目卡常数(我大战常数两小时)，矩阵我都是手推的。
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long ll;
#define maxn (1000010)
#define rhl (1000000007)
char s[maxn]; int A,B,C,D;
struct Matrix
{
ll s[2][2]; short a,b;
inline Matrix() { memset(s,0,sizeof(s)); }
}M1,M2;
struct bignum
{
short a[maxn];int l;
inline void read()
{
scanf("%s",s); l = strlen(s);
for (int i = l;i;--i) a[i] = s[i-1]-'0';
}
inline void dec()
{
a[l]--;
for (int i = l;i;--i) { if (a[i] < 0) a[i-1]--,a[i] += 10; else break; }
if (a[1] == 0) { for (int i = 2;i <= l;++i) a[i-1] = a[i]; a[l--] = 0; }
}
}n,m;
inline Matrix times(const Matrix &x,const Matrix &y)
{
Matrix ret; ret.a = x.a; ret.b = y.b;
if (ret.a == 1)
{
ret.s[0][0] = x.s[0][0]*y.s[0][0]+x.s[0][1]*y.s[1][0];
if (ret.s[0][0] >= rhl) ret.s[0][0] %= rhl;
ret.s[0][1] = 1;
}
else
{
ret.s[0][0] = x.s[0][0]*y.s[0][0]+x.s[0][1]*y.s[1][0];
ret.s[1][0] = x.s[1][0]*y.s[0][0]+x.s[1][1]*y.s[1][0];
if (ret.s[0][0] >= rhl) ret.s[0][0] %= rhl;
if (ret.s[1][0] >= rhl) ret.s[1][0] %= rhl;
ret.s[1][1] = 1;
}
return ret;
}
inline Matrix ksm(Matrix a,int b)
{
Matrix ret; ret.a = ret.b = 2;
ret.s[0][0] = ret.s[1][1] = 1;
for (;b;b >>= 1,a = times(a,a)) if (b & 1) ret = times(ret,a);
return ret;
}
inline Matrix qsm(Matrix a,const bignum &b)
{
Matrix ret; ret.a = ret.b = 2;
ret.s[0][0] = ret.s[1][1] = 1;
for (int i = b.l;i;--i) ret = times(ret,ksm(a,b.a[i])),a = ksm(a,10);
return ret;
}
int main()
{
freopen("3240.in","r",stdin);
freopen("3240.out","w",stdout);
n.read(); m.read(); scanf("%d %d %d %d",&A,&B,&C,&D);
n.dec(); m.dec();
Matrix ans,mul;
ans.a = 1; ans.b = 2; ans.s[0][0] = 1; ans.s[0][1] = 1;
M1.a = M2.a = M1.b = M2.b = 2;
M1.s[0][0] = A; M1.s[1][1] = 1; M1.s[1][0] = B;
mul.a = mul.b = 2;
mul.s[0][0] = C; mul.s[1][1] = 1; mul.s[1][0] = D;
M2 = times(qsm(M1,m),mul);
ans = times(ans,qsm(M2,n)); ans = times(ans,qsm(M1,m));
printf("%lld",ans.s[0][0]);
fclose(stdin); fclose(stdout);
return 0;
}