首页 > 代码库 > HDU 1757 A Simple Math Problem

HDU 1757 A Simple Math Problem

2024-07-25 02:47:37   215人阅读

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 99991 1 1 1 1 1 1 1 1 120 5001 0 1 0 1 0 1 0 1 0
 
Sample Output
45104
 

 

典型的矩阵快速幂递推。

很典型地构造一个

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;    }}

 

HDU 1757 A Simple Math Problem


联系
我们