HDU 1757-A Simple Math Problem(矩阵快速幂)

A Simple Math Problem

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit  Status  Practice  HDU 1757

Appoint description:  System Crawler  (2015-03-04)

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 
     
     

题意：就是两个式子
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);  求值。

思路：这算是初步学会如何构造矩阵了吧，其实也没什么难得，主要是想不好想，唉，还是自己太弱了。

x<10的时候好说，下面就说一下n>=10的情况。如下图

矩阵A                                                   矩阵B


0 1 0 0 0 0 0 0 0 0                                  f0                                  f1


0 0 1 0 0 0 0 0 0 0                                  f1                                  f2


0 0 0 1 0 0 0 0 0 0                                  f2                                  f3


0 0 0 0 1 0 0 0 0 0                *                f3  ---------->                f4


0 0 0 0 0 1 0 0 0 0                                  f4                                  f5


0 0 0 0 0 0 1 0 0 0                                  f5                                  f6


0 0 0 0 0 0 0 1 0 0                                  f6                                  f7


0 0 0 0 0 0 0 0 1 0                                  f7                                  f8


0 0 0 0 0 0 0 0 0 1                                  f8                                  f9


a9 a8 a7 a6 a5 a4 a3 a2 a1 a0                  f9                                  f10


我们看到规律了，每次要到下次个A*B，以此类推则由A*A*A.......A*B；

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f;
int mod;
int a[20];
struct node {
    int mp[20][20];
} init,res;
struct node Mult(struct node x,struct node y)
{
    struct node tmp;
    int i,j,k;
    for(i=0; i<10; i++)
        for(j=0; j<10; j++) {
            tmp.mp[i][j]=0;
            for(k=0; k<10; k++) {
                tmp.mp[i][j]=(tmp.mp[i][j]+x.mp[i][k]*y.mp[k][j])%mod;
            }
        }
    return tmp;
};
struct node expo(struct node x,int k)
{
    struct node tmp;
    int i,j;
    for(i=0; i<10; i++)
        for(j=0; j<10; j++) {
            if(i==j)
                tmp.mp[i][j]=1;
            else
                tmp.mp[i][j]=0;
        }
    while(k) {
        if(k&1) tmp=Mult(tmp,x);
        x=Mult(x,x);
        k>>=1;
    }
    return tmp;
};
int main()
{
    int k,x,i,j;
    while(~scanf("%d %d",&k,&mod)) {
        if(k<10) {
            printf("%d\n",k%mod);
            continue ;
        }
        for(i=9; i>=0; i--)
            a[i]=9-i;
        for(i=0; i<10; i++) {
            scanf("%d",&x);
            init.mp[0][i]=x%mod;
        }
        for(i=1; i<10; i++) {
            for(j=0; j<10; j++) {
                if(i==j+1)
                    init.mp[i][j]=1;
                else
                    init.mp[i][j]=0;
            }
        }
        res=expo(init,k-9);
        int ans=0;
        for(j=0; j<10; j++) {
            ans=(ans+res.mp[0][j]*a[j])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}