hdu 1757 A Simple Math Problem

简介:

点击此处即可传送到hdu 1757

                        **A Simple Math Problem**
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3497    Accepted Submission(s): 2112



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

题目大意:给你两个数,k,mod,
然后再有是个数a[i],就是求 f(k) % mod
解题思路:很简单,就是用一下那个矩阵乘法和快速幂就行了,就是套模板,具体详见我代码:

上代码:

/*
2015 - 8 - 15 下午
Author: ITAK

今天感觉还可以,买了一个机械键盘,又要少吃几顿饭了。。。

今日的我要超越昨日的我,明日的我要胜过今日的我,
以创作出更好的代码为目标,不断地超越自己。
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 10;
int mod;
typedef long long LL;
typedef  struct
{
    int  m[maxn][maxn];
}  Matrix;
//定义一个10*10的矩阵
Matrix P= {0,0,0,0,0,0,0,0,0,0,
           1,0,0,0,0,0,0,0,0,0,
           0,1,0,0,0,0,0,0,0,0,
           0,0,1,0,0,0,0,0,0,0,
           0,0,0,1,0,0,0,0,0,0,
           0,0,0,0,1,0,0,0,0,0,
           0,0,0,0,0,1,0,0,0,0,
           0,0,0,0,0,0,1,0,0,0,
           0,0,0,0,0,0,0,1,0,0,
           0,0,0,0,0,0,0,0,1,0
          };
Matrix I= {1,0,0,0,0,0,0,0,0,0,
           0,1,0,0,0,0,0,0,0,0,
           0,0,1,0,0,0,0,0,0,0,
           0,0,0,1,0,0,0,0,0,0,
           0,0,0,0,1,0,0,0,0,0,
           0,0,0,0,0,1,0,0,0,0,
           0,0,0,0,0,0,1,0,0,0,
           0,0,0,0,0,0,0,1,0,0,
           0,0,0,0,0,0,0,0,1,0,
           0,0,0,0,0,0,0,0,0,1
          };
//矩阵乘法
Matrix matrix_mul(Matrix a, Matrix b)
{
    int i,j,k;
    Matrix c;
    for(i=0; i<maxn; i++)
    {
        for(j=0; j<maxn; j++)
        {
            c.m[i][j] = 0;
            for(k=0; k<maxn; k++)
                c.m[i][j] += (a.m[i][k]*b.m[k][j])%mod;
            c.m[i][j] %= mod;//及时取余
        }
    }
    return c;
}
//矩阵的快速幂
Matrix quick_mod(LL m)
{
    Matrix ans = I, b = P;
    while(m)
    {
        if(m & 1)
            ans = matrix_mul(ans,b);
        m >>= 1;
        b = matrix_mul(b, b) ;
    }
    return ans;
}
int a[10];
int main()
{
    int k;
    while(~scanf("%d%d",&k,&mod))
    {
        for(int i=0; i<10; i++)
        {
            scanf("%d",&a[i]);
            P.m[0][i] = a[i];//给矩阵赋值
        }
        if(k < 10)
            printf("%d\n",k%mod);
        else
        {
            int sum = 0;
            Matrix tmp = quick_mod(k-9);
            for(int j=9; j>=0; j--)
                sum = (sum+tmp.m[0][9-j]*j)%mod;//不要最后加一边加,一边取余
            cout<<sum<<endl;
        }
    }
    return 0;
}
目录
相关文章
|
图形学
hdu1086 You can Solve a Geometry Problem too(判断线段相交)
hdu1086 You can Solve a Geometry Problem too(判断线段相交)
71 0
A1947 An Olympian Math Problem
Alice, a student of grade 66, is thinking about an Olympian Math problem, but she feels so despair that she cries. And her classmate, Bob, has no idea about the problem. Thus he wants you to help him. The problem is:
87 0
A1947 An Olympian Math Problem
【HDU 5572 An Easy Physics Problem】计算几何基础
2015上海区域赛现场赛第5题。 题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5572 题意:在平面上,已知圆(O, R),点B、A(均在圆外),向量V。
1038 0