`
hellojyj
  • 浏览: 61719 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

HDU 1757 A Simple Math Problem

    博客分类:
  • ACM
阅读更多

原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1757

A Simple Math Problem

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2480    Accepted Submission(s): 1441


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

 

 

 

 

Recommend

 

lcy   |   We have carefully selected several similar problems for you:  1588 3117 2276 2256 2604
分析:这道题如果用打表或者递归肯定都是TLE的,那么我们可以用什么办法解决呢。。答案当然是矩阵快速幂。关键在于矩阵怎么构造了= =,这个矩阵也不难构造,就拿第一个例子来说,我们可以构造矩阵
1  1  1  1  1  1  1  1  1  1
    1            0
         1
    0       。
                      。
                               1   0
只要学过矩阵乘法运算,估计都应该已经知道怎么回事了!
 
#include<cstdio>
#include<cstring>
int k,m,ans;
struct Matrix{
    int mat[10][10];
    Matrix operator *(const Matrix rhs) const {
        Matrix temp;
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                temp.mat[i][j] = 0;
                for(int k=0;k<10;k++){
                    temp.mat[i][j] += (this->mat[i][k] * rhs.mat[k][j])%m;
                    temp.mat[i][j] %= m;
                }
            }
        }
        return temp;
    }
};

Matrix ret,mt;
int main(){
    while(~scanf("%d%d",&k,&m))
    {
        ans = 0;
        memset(ret.mat,0,sizeof(ret.mat));
        memset(mt.mat,0,sizeof(mt.mat));
        for(int i=0;i<10;i++)
            ret.mat[i][i] = 1;
        for(int i=0;i<10;i++)
            scanf("%d",&mt.mat[0][i]);
        for(int i=1;i<10;i++)
            mt.mat[i][i-1] = 1;
        k = k-9;
        while(k)
        {
            if(k&1) ret = ret * mt;
            k>>=1;
            mt = mt*mt;
        }
        for(int i=0;i<10;i++)
            ans = (ans + ret.mat[0][i]*(9-i))%m;
        printf("%d\n",ans);
    }

    return 0;
}
0
1
分享到:
评论

相关推荐

    HDU 1022 Train Problem I 附详细思路

    HDU 1022 Train Problem I 附详细思路

    hdu-api:A simple SDK for HDU. 一个提供一卡通服务、考试、课表、选课和公共信息等 API 的 SDK

    A simple SDK for HDU. hdu-api 是一个集结 HDU 所有教务管理服务的 SDK,提供了一卡通服务、考试、课表、选课和一些公共信息如空闲教室、上课时间等信息的 API。 hdu-api 主要基于 Requests 库和 Beautiful Soup 库...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    - 这个函数接收两个字符串参数`a`和`b`,代表两个待相加的大整数,以及一个整数`fn`作为结果存放的位置索引。 - 函数内部首先计算两个数的长度,然后进行逐位相加,同时考虑进位的情况。 - 结果存储在一个临时的`...

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo.zip

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo

    hdu 1753 大明A+B

    Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    HDU1019(2028)解题报告

    The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number ...

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    考试类精品--A simple SDK for HDU. 一个提供一卡通服务、考试、课表、选课和公共信息等 API .zip

    【标题】中的"A simple SDK for HDU"是一个专为杭州电子科技大学(HDU)设计的简单SDK,它提供了丰富的功能接口,包括一卡通服务、考试管理、课程表、选课系统以及公共信息查询等。这样的SDK对于开发者来说,是构建...

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

Global site tag (gtag.js) - Google Analytics