#2354. 组合数问题

    ID: 2354 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>PROV赛事:contest388来源:qoj.ac数据:公开样例数学快速幂

组合数问题

组合数问题

题目描述

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试组合数问题(problem) 组合数问题(problem) 【问题描述】 组合数Cm n 表示的是从n 个互不相同的物品中选出m 个物品的方案数。举个例子, 从(1, 2, 3) 三个物品中选择两个物品可以有(1, 2), (1, 3), (2, 3) 这三种选择方法。根据组 合数的定义,我们可以给出计算组合数Cm n 的一般公式: Cm n = n! m!(n −m)! 其中n! = 1 × 2 × · · · × n。(特别的,当n = 0 时,n! = 1 ,当m > n 时,Cm n = 0) 小葱在NOIP 的时候学习了C j i 和k 的倍数关系,现在他想更进一步,研究更多 关于组合数的性质。小葱发现,C j i 是否是k 的倍数,取决于C j i mod k 是否等于0,这 个神奇的性质引发了小葱对mod 运算(取余数)的兴趣。现在小葱选择了是四个整数 n, p, k, r,小葱现在希望知道  ∞ ∑ i=0 Cik+r nk mod p 即 ( Cr nk + Ck+r nk + C2k+r nk

  • · · · + C(n−1)k+r nk
  • Cnk+r nk
  • · · · ) mod p 的值。 【输入格式】 从文件problem.in 中读入数据。 第一行有四个整数n, p, k, r,所有整数含义见问题描述。 【输出格式】 输出到文件problem.out 中。 一行一个整数代表答案。 【样例1 输入】 2 10007 2 0 【样例1 输出】 8 第8 页 共9 页

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试组合数问题(problem) 【样例1 说明】 C0 4 + C2 4 + C4 4 + · · · = 1 + 6 + 1 = 8 【样例2 输入】 20 10007 20 0 【样例2 输出】 176 【子任务】 • 对于30% 的测试点,1 ≤n, k ≤30,p 是质数; • 对于另外5% 的测试点,p = 2; • 对于另外5% 的测试点,k = 1; • 对于另外10% 的测试点,k = 2; • 对于另外15% 的测试点,1 ≤n ≤103, 1 ≤k ≤50,p 是质数; • 对于另外15% 的测试点,1 ≤n × k ≤106,p 是质数; • 对于另外10% 的测试点,1 ≤n ≤109, 1 ≤k ≤50,p 是质数; • 对于100% 的测试点,1 ≤n ≤109, 0 ≤r < k ≤50, 2 ≤p ≤230 −1。 第9 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 10007 2 0
8

样例 2

20 10007 20 0
176