bzoj 3240 矩阵乘法+十进制快速幂

首先，构造出从f[][i]->f[][i+1]的转移矩阵a，和从f[i][m]->f[i+1][1]的转移矩阵b，

那么从f[1][1]转移到f[n][m]就是init*(a^(m-1)*b)^(n-1)*(a^(m-1))。

然后用用十进制快速幂（因为输入用的是10进制，这样就避免了高精度除法）。

第一次写十进制快速幂，大概的思想是维护当前位是1～9的要乘的矩阵，然后再通过这9个矩阵自己转移。

 /**************************************************************
     Problem: 3240
     User: idy002
     Language: C++
     Result: Accepted
     Time:5352 ms
     Memory:2764 kb
 ****************************************************************/ #include <cstdio>
 #include <cstring>
 #include <cctype>
 #include <algorithm>
 #define N 1000010
 #define Mod 1000000007
 using namespace std; typedef long long dnt;
 struct Matrix {
     dnt v[][];
     void make_unit() {
         for( int i=; i<; i++ )
             for( int j=; j<; j++ )
                 v[i][j] = (i==j);
     }
     inline const dnt* operator[]( int i ) const { return v[i]; }
     Matrix(){}
     Matrix( int aa, int ab, int ba, int bb ) {
         v[][] = aa, v[][] = ab, v[][] = ba, v[][] = bb;
     }
     Matrix operator*( const Matrix &b ) const {
         const Matrix &a = *this;
         return Matrix( , (b[][]+a[][]*b[][])%Mod,
                        , a[][]*b[][]%Mod );
     }
     Matrix operator^( const char *b ) const {
         Matrix rt, q[];         q[] = *this;
         for( int i=; i<=; i++ )
             q[i] = q[i-]*q[];         rt.make_unit();
         for( int i=; b[i]; i++ ) {
             if( b[i]-'' ) rt = rt*q[b[i]-''];
             q[] = q[]*q[];
             for( int j=; j<=; j++ )
                 q[j] = q[j-]*q[];
         }
         return rt;
     }
 }; char sn[N], sm[N];
 int ln, lm;
 int a, b, c, d;
 Matrix ma, mb, ans; void subone( char s[] ) {
     int i = ;
     s[i]--;
     while( s[i]<'' ) {
         s[i] += ;
         s[i+]--;
         i++;
     }
 }
 int main() {
     scanf( "%s%s%d%d%d%d", sn, sm, &a, &b, &c, &d );
     ln = strlen(sn), lm = strlen(sm);
     reverse( sn, sn+ln );
     reverse( sm, sm+lm );
     subone(sn), subone(sm);
     ma = Matrix(,b,,a)^sm;
     mb = Matrix(,d,,c);
     ans = ((ma*mb)^sn)*ma;
     printf( "%lld\n", (ans[][]+ans[][]) % Mod );
 }