A Simple Math Problem

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

Total Submission(s): 155 Accepted Submission(s): 110

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

Author

linle

Source

2007省赛集训队练习赛（6）_linle专场

Recommend

lcy

/*

题意：给你题目描述的函数，然后让你求f(k)%m的值

初步思路：简单的爆一下

#错误:超内存！

#改进思路：

    想一下这个式子的实质，不用递归写，用循环写，但是需要循环1e9次，肯定是不可行的,可以用矩阵相乘f(x)是从0，1，2...9乘上a0,a1,a2...

    .a9递推过来的这样就能得出来一个矩阵，线性代数还没学，矩阵真的有点麻烦，构造矩阵的时候老是想错了。

#再次错误：矩阵相乘虽然可以解决空间问题，但是没法解决时间问题；这里真的有点糊涂了，常数都有快速幂，矩阵的快速幂怎么就没有想起来呐！

*/

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll m,k;

struct Matrix{

    ll m[][];

    void init0(){//构造用来乘的矩阵(相当于“幺元”吧，随便想到了离散中的概念就这么叫吧)

        memset(m,,sizeof m);

        for(int i=;i<;i++)

            m[i][i-]=;

    }

    void init1(){//构造最初的a0~a9

        memset(m,,sizeof m);

        for(int i=;i<;i++){

            m[i][]=-i;

        }

    }

};

Matrix Mul_Matrix(Matrix a,Matrix b){

    Matrix c;

    c.init0();

    for(int i=;i<;i++){

        for(int j=;j<;j++){

            c.m[i][j]=;

            for(int k=;k<;k++){

                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%m;

            }

            c.m[i][j]%=m;

        }

    }

    return c;

}

/**************矩阵快速幂*********************/

Matrix Pow(Matrix a,Matrix b,int x){

    while(x){

        if(x&){

            b=Mul_Matrix(a,b);

        }

        a=Mul_Matrix(a,a);

        x>>=;

    }

    return b;

}

/**************矩阵快速幂*********************/

Matrix a,b;

int main(){

    //freopen("in.txt","r",stdin);

    while(scanf("%lld%lld",&k,&m)!=EOF){

        a.init0();

        b.init1();

        //cout<<k<<" "<<m<<endl;

        for(int i=;i<;i++) scanf("%lld",&a.m[][i]);

        // for(int i=9;i<k;i++){

            // b=Mul_Matrix(a,b);

            // for(int i=0;i<10;i++){

                // for(int j=0;j<10;j++)

                    // cout<<a.m[i][j]<<" ";

                // cout<<"         ";

                // for(int j=0;j<10;j++)

                    // cout<<b.m[i][j]<<" ";

                // cout<<endl;

            // }

        // }

        Matrix c=Pow(a,b,k-);//利用矩阵快速幂

        printf("%lld\n",c.m[][]);

    }

    return ;

}

A9

A Simple Math Problem（矩阵快速幂）（寒假闭关第一题，有点曲折啊）

A Simple Math Problem