P2481 [SDOI2010]代码拍卖会

    • 98通过
    • 334提交
  • 题目提供者 woyaobaidu
  • 评测方式 云端评测
  • 标签 数位动规,数位dp 组合数学 各省省选 2010 山东 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    随着iPig在P++语言上的造诣日益提升,他形成了自己一套完整的代码库。猪王国想参加POI的童鞋们都争先恐后问iPig索要代码库。iPig不想把代码库给所有想要的小猪,只想给其中的一部分既关系好又肯出钱的小猪,于是他决定举行了一个超大型拍卖会。

    在拍卖会上,所有的N头小猪将会按照和iPig的好感度从低到高,从左到右地在iPig面前站成一排。每个小猪身上都有9猪币(与人民币汇率不明),从最左边开始,每个小猪依次举起一块牌子,上面写上想付出的买代码库的猪币数量(1到9之间的一个整数)。大家都知道,如果自己付的钱比左边的猪少,肯定得不到梦寐以求的代码库,因此从第二只起,每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪(们)会得到iPig的代码库真传,向着保送PKU(Pig Kingdom University)的梦想前进。

    iPig对自己想到的这个点子感到十分满意,在去现场的路上,iPig就在想象拍卖会上会出现的场景,例如一共会出现多少种出价情况之类的问题,但这些问题都太简单了,iPig早已不敢兴趣了,他想要去研究更加困难的问题。iPig发现如果他从台上往下看,所有小猪举的牌子从左到右将会正好构成一个N位的整数,他现在想要挑战的问题是所有可能构成的整数中能正好被P整除的有多少个。由于答案过大,他只想要知道答案mod 999911659就行了。

    输入输出格式

    输入格式:

    输入文件auction.in有且仅有一行:两个数N(1≤N≤10^18)、P(1≤P≤500),用一个空格分开。

    输出格式:

    输入文件auction.out有且仅有一行:一个数,表示答案除以999911659的余数。

    输入输出样例

    输入样例#1: 复制
    2 3
    输出样例#1: 复制
    15

    说明

    样例解释

    方案可以是:12 15 18 24 27 33 36 39 45 48 57 66 69 78 99,共15种。

    数据规模

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。