洛谷P3807 【模板】卢卡斯定理exgcd

2018-02-07 20:14:43来源:cnblogs.com作者:自为风月马前卒人点击

分享

题目背景

这是一道模板题。

题目描述

给定n,m,p(1/le n,m,p/le 10^51≤n,m,p≤105 )

求 C_{n+m}^{m}/ mod/ pCn+mm​ mod p

保证P为prime

C表示组合数。

一个测试点内包含多组数据。

输入输出格式

输入格式:

第一行一个整数T(T/le 10T≤10 ),表示数据组数

第二行开始共T行,每行三个数n m p,意义如上

输出格式:

共T行,每行一个整数表示答案。

Lucas定理这个东西就不细学了。

毕竟就一行代码,辣么好背

$/begin{pmatrix} n // m /end{pmatrix}modp=/begin{pmatrix} n & modp // m & modp /end{pmatrix}/ast /begin{pmatrix} /dfrac {n}{p} // /dfrac {m}{p} /end{pmatrix}modp$

输入输出样例

输入样例#1: 复制
21 2 52 1 5
输出样例#1: 复制
33





最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台