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
1<=N,M<=10^1000 000,a<=a,b,c,d<=10^9
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
费马小定理+逆元+快速幂~
看似是一个矩阵裸题，实际上却和矩阵没什么关系，因为……n,m太大了。
这里就要用到费马小定理，a^(p-1)≡1(mod p)，然后输入的时候转化一下就可以了。
另外就是直接递推的话很麻烦，这里可以手推公式，在网上找了一个讲得很详细的图：
（来自http://www.cnblogs.com/iiyiyi/p/5617598.html，莫名其妙变得很大，不习惯的话可以看原博文~）
然后照做就可以了~
（逆元就是n/m=n*mi(m)，其中mi(m)=m^(mod-2)~）
大小字母要区分，取模要取够，最后输出的时候要再加上一个mod防止变成负数。
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define ll long long #define modd 1000000007ll a,b,c,d,f,D; char s[1000005];struct node{ll num,zer; }n,m;ll mi(ll u,ll v) {ll ans=1;while(v){if(v&1) ans=(ans*u)%modd;v>>=1;u=(u*u)%modd;}return ans; }ll ni(ll u) {return mi(u,modd-2); }node getnum() {int len=strlen(s);node u=(node){0,0};for(int i=0;i<len;i++){u.num=((u.num*10)%(modd-1)+s[i]-'0')%(modd-1);u.zer=((u.zer*10)%modd+s[i]-'0')%modd;}return u; }int main() {scanf("%s",s);n=getnum();scanf("%s",s);m=getnum();scanf("%lld%lld%lld%lld",&a,&b,&c,&d);if(a==1){D=((((c*(m.zer-1))%modd)*b)%modd+d)%modd;if(c==1) f=(1+n.zer*D)%modd;else{ll cn=mi(c,n.num);f=(cn+((((D*(cn-1))%modd)*ni(c-1))%modd))%modd;}}else{ll am=mi(a,m.num-1);ll A=(am*c)%modd;ll B=((((((b*c)%modd)*(am-1))%modd)*ni(a-1))%modd+d)%modd;ll an=mi(A,n.num);f=an+((B*(an-1)%modd)*ni(A-1))%modd;}printf("%lld\n",(((f-d)*ni(c))%modd+modd)%modd);return 0; }