专栏首页数据结构与算法洛谷 P3807 【模板】卢卡斯定理

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

题目背景

这是一道模板题。

题目描述

给定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行,每行一个整数表示答案。

输入输出样例

输入样例#1: 

2
1 2 5
2 1 5

输出样例#1:

3
3

卢卡斯定理
$C(n,m)%p=C(n%p,m%p)*C(n/p,m/p)$
对于这道题来说,p是素数,解逆元的时候用快速幂
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define LL long long 
 6 using namespace std;
 7 const LL MAXN=1e6+10;
 8 const LL INF=0x7fffff;
 9 inline LL read()
10 {
11     char c=getchar();LL flag=1,x=0;
12     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
13     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*flag;
14 }
15 LL js[MAXN];
16 LL fastpow(LL a,LL p,LL mod)
17 {
18     LL base=1;
19     while(p)
20     {
21         if(p&1)    base=(base*a)%mod;
22         a=(a*a)%mod;
23         p>>=1;
24     }
25     return base;
26 }
27 LL C(LL n,LL m,LL mod)
28 {
29     if(m>n)    return 0;
30     return js[n]*fastpow(js[m],mod-2,mod)*fastpow(js[n-m],mod-2,mod)%mod;
31 }
32 LL Lucas(LL n,LL m,LL mod)
33 {
34     if(m==0)    return 1;
35     else return C(n%mod,m%mod,mod)*(Lucas(n/mod,m/mod,mod))%mod;
36 }
37 int main()
38 {
39     LL T=read();
40     js[0]=1;
41     while(T--)
42     {
43         LL n=read(),m=read(),mod=read();
44         for(LL i=1;i<=mod;i++)    js[i]=(js[i-1]*i)%mod;
45         printf("%lld\n",Lucas(n+m,m,mod)%mod);
46     }
47     return 0;
48 }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 机器人SLAM算法漫谈

    1. 前言   开始做SLAM(Simultaneous Localization and Mapping,机器人同时定位与建图)研究已经近一年了。从一年级开始...

    智能算法
  • 小波系数

    1. 求小波变化系数时a b怎么取? 小波变换的概念是由法国从事石油信号处理的工程师J.Morlet在1974年首先提出的,通过物理的直观和信号处理的实际需要经...

    互联网金融打杂
  • 人脸识别经典算法:特征脸方法(Eigenface)

    特征脸方法基本是将人脸识别推向真正可用的第一种方法,了解一下还是很有必要的。特征脸用到的理论基础PCA在之前的文章中已经讲过了。直接上特征脸方法的步骤:...

    智能算法
  • Java基础知识学习笔记(一)

      理解面向对象: Java纯粹的面向对象的程序设计语言,主要表现为Java完全支持面向对象的三个基本特征:继承、封装、多态。 Java程序的最小单位是类,类代...

    互联网金融打杂
  • 没有公式如何看懂EM算法?

    EM(Expectation Maximization: 期望最大化)这个问题感觉真的不太好用通俗的语言去说明白,因为它很简单,又很复杂。简单在于它的思想,简单...

    智能算法
  • 分类回归树算法---CART

    一、算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相...

    智能算法
  • 挖掘关联规则之Apriori算法

    1. Apriori算法的目的: 主要是用来挖掘关联规则,即从一个事务数据集中发现频繁项集并推出关联规则,其名字是因为算法基于先验知识(prior knowle...

    智能算法
  • 遗传算法如何模拟大自然的进化?

    遗传算法 ( GA , Genetic Algorithm ) ,也称进化算法 。 遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法...

    智能算法
  • 分类算法之朴素贝叶斯分类(Naive Bayesian classification)

    如果用一句话来概括贝叶斯分类器,那就是:根据样本集中的先验信息,来推算出某一个样本属于某一类的概率,然后根据推算出来的结果将该样本分为某类 。贝叶斯分类是一类分...

    智能算法
  • 程序员面试50题(1)—查找最小的k个元素[算法]

    题目:输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。 分析:这道题最简单的思路莫过于把输...

    互联网金融打杂

扫码关注云+社区

领取腾讯云代金券