HDU 1757 A Simple Math Problem

A Simple Math Problem

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 108 Accepted Submission(s): 77

Problem Description

Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.

 

Input

The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.

 

Output

            For each case, output f(k) % m in one line.

 

Sample Input

10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

 

Sample Output

45
104

 

典型的矩阵快速幂递推。

很典型地构造一个

f(n-1)    f(n-2)    f( n-3)  ....... f(n-10 )                       a0   1   0  0  0 ..........0  0 

 0             0             0      ........    0                            a1   0   1  0  0 ..........0  0 

......................................................              X           .......................................

 ....................................................                            a8  0  0  0 ...............0   1       

0             0             0      ........    0                             a9   0  0  0 ..............0   0

这样的矩阵来递推输出 最后一个矩阵的 （ 0 ， 0 ）位置的数就OK了~

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 12 ;
int n , mod , x[N];

struct Mat
{
    int c[N][N];
    Mat(){ memset( c , 0 , sizeof c ); };
    Mat operator * (const Mat &a )const{
        Mat res ;
        for( int i = 0 ; i < 10 ; ++i ){
            for( int k = 0 ; k < 10 ; ++k ){
                if( !c[i][k] ) continue ;
                for( int j = 0 ; j < 10 ; ++j ){
                    res.c[i][j] += c[i][k] * a.c[k][j] ;
                    res.c[i][j] %= mod;
                }
            }
        }
        return res ;
    }
    void print(){
        for( int i =0 ; i < 10 ;++i ){
            for( int j = 0 ; j < 10 ;++j ){
                cout << c[i][j] <<' ';
            }
            cout<<endl;
        }
    }
};

Mat quick_mod( Mat a , LL n )
{
    Mat res = a ;
    while(n)
    {
        if( n & 1 )  res = res * a;
        a = a * a ;
        n >>= 1 ;
    }
    return res;
}

int main()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while( cin >> n >> mod ){
        for( int i = 0; i < 10 ; ++i ){
            cin >> x[i] ;
        }
        if( n < 10 ){
            cout << ( n % mod ) <<endl;
            continue ;
        }
        Mat a ,res ;
        for( int i = 0 ; i < 10 ; ++i )
            res.c[0][i] = ( 9 - i );
        for( int i = 0 ; i < 10 ; ++i ){
            a.c[i][0] = x[i] ;
            if( i < 9 ) a.c[i][i+1] = 1;
        }
//        res.print();cout<<endl;
//        a.print();cout<<endl;
//        a = res * a;
//        a.print();cout<<endl;
        res = res * quick_mod( a , n - 10 ) ;
//        res.print();cout<<endl;
        cout << res.c[0][0] <<endl;
    }
}