跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0187. #2143. 「SHOI2017」组合数问题

  • ID: 193
  • 传统题
  • 1000ms
  • 512MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#2143. 「SHOI2017」组合数问题

题目描述

组合数 表示的是从 个互不相同的物品中选出 个物品的方案数。举个例子, 从 三个物品中选择两个物品可以有 ,, 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 的一般公式:

Cmn=n!m! (n−m)!

其中 。(特别地,当 时,;当 时,。)

小葱在 NOIP 的时候学习了 和 的倍数关系,现在他想更进一步,研究更多关于组合数的性质。小葱发现, 是否是 的倍数,取决于 Cjimodk 是否等于 ,这个神奇的性质引发了小葱对 运算(取余数运算)的兴趣。现在小葱选择了是四个整数 ,他希望知道

(∞∑i=0Cik+rnk)modp,

即

(Crnk+Ck+rnk+C2k+rnk+⋯+C(n−1)k+rnk+Cnk+rnk+⋯)modp

的值。

输入格式

第一行有四个整数 ,所有整数含义见问题描述。

输出格式

一行一个整数代表答案。

样例

样例输入 1

2 10007 2 0

样例输出 1

8

样例解释 1

。

样例输入 2

20 10007 20 0

样例输出 2

176

数据范围与提示

对于 的测试点,, 是质数;
对于另外 的测试点,;
对于另外 的测试点,;
对于另外 的测试点,;
对于另外 的测试点,, 是质数;
对于另外 的测试点,, 是质数;
对于另外 的测试点,, 是质数;
对于 的测试点,。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 73 题。保留原作者与原赛事署名。