欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-18 16:28:33
题目背景 这是一道模板题。 题目描述 给定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\l ......

题目背景

这是一道模板题。

题目描述

给定n,m,p(1\le n,m,p\le 10^51n,m,p105 )

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

保证P为prime

C表示组合数。

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

输入输出格式

输入格式:

 

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

第二行开始共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: 复制
2
1 2 5
2 1 5
输出样例#1: 复制
3
3