P5224 Candies

    • 19通过
    • 451提交
  • 题目提供者 暮雪﹃紛紛
  • 评测方式 云端评测
  • 标签 O2优化
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    JerryC有一大袋糖果,他正以$1\ t/ms$的速度食用着这一袋糖果......

    题目描述

    JerryC的糖果有$N$箱(两两之间不同)。他一开始想挑$M$箱出来,但是觉得吃起来不过瘾,所以又想要多拿一些出来。由于他比较喜欢数字$K$,所以只要拿出来的糖的量$x(x \ge M)$满足:$x \equiv M\ (\bmod\ K)$,JerryC就会得到满足感。

    求有多少种方案使得JerryC得到满足感。请输出方案数$\bmod\ 1004535809$的结果。

    输入输出格式

    输入格式:

    一行三个非负整数$N$,$M$,$K$。

    输出格式:

    一行一个非负整数,表示方案数$\bmod\ 1004535809$的结果。

    输入输出样例

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

    说明

    样例解释:

    可以拿出来:2箱 5箱 8箱,组合数算一下就是了:

    $$\binom{10}{2}+\binom{10}{5}+\binom{10}{8}=342$$

    数据范围:

    测试点编号 $N\le$ $K\le$
    $1$ $1$ $1$
    $2-3$ $10^6$ $10$
    $4-8$ $10^{12}$ $100$
    $9-12$ $10^{15}$ $10^3$
    $12-20$ $10^{18}$ $10^4$

    $$0 \leq M < K$$

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