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

题目背景

这是一道模板题。

题目描述

给定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: 

2
1 2 5
2 1 5

输出样例#1:

3
3

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏null的专栏

挑战数据结构和算法——栈的push、pop序列

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题考查栈的基本操作,栈是一种“先进后出”的数据结构。判...

34060
来自专栏ACM算法日常

交错字符串(动态规划)- leetcode 97

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

17710
来自专栏吴伟祥

认识XPath(确定XML文档中某部分位置的语言)

XPath即为XML路径语言(XML Path Language),它是一种用来确定XML文档中某部分位置的语言。

8810
来自专栏算法channel

Tensorflow|通过Variable及assign()感悟一点设计之道

01 Variable a = tf.Variable(2, name="scalar") # create variable a with scalar v...

2.2K70
来自专栏Java爬坑系列

C\C++ 生成各位数不相等的随机数

  最近想写一个1A2B的小游戏来练习一下,结果在第一步生成随机数的时候就遇到了一点点问题。   游戏初始化时需要先生成一个四位随机数,且各位各不相等。于是最开...

29770
来自专栏小鹏的专栏

Pandas处理csv表格

可以结合这篇使用:数据处理利器Pandas使用手册 1)读取csv文件 data =pandas.read_csv(‘test.csv’) //返回的是Data...

59450
来自专栏程序生活

美团NLP实习面试总结一 基本知识4 数据结构二 NLP相关技术1 LSTM2 介绍实体链接与实体映射3 解释随机游走的原理及作用4 命名实体识别

机会总是留给有准备的人 一 基本知识 1 python 解释下装饰器和生成器的作用以及用法 类的知识点,类与对象,三个输出 2 java HashMap的实现原...

46230
来自专栏程序员的知识天地

Python实现随机生成验证码?小菜一碟!

Python随机生成验证码的方法有很多,今天给大家列举两种,大家也可以在这个基础上进行改造,设计出适合自己的验证码方法

16320
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

458100
来自专栏二进制文集

LeetCode 动态规划 题目分类汇总

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

40060

扫码关注云+社区

领取腾讯云代金券