luoguP3807 【模板】卢卡斯定理

﹏ヽ暗。殇╰゛Y 2021-09-29 09:52 266阅读 0赞

www.cnblogs.com/shaokele/

--------------------

> ## luoguP3807 【模板】卢卡斯定理 ##
> 
> 　　Time Limit: 1 Sec  
> 　　Memory Limit: 128 MB
> 
> ### Description ###
> 
> 　　给定n,m,p \\((1≤ n,m,p ≤ 10^5)\\)  
> 　　求 \\\[C\_\{n+m\}^\{m\}\\ mod\\ p\\\]  
> 　　保证P为prime  
> 　　C表示组合数。  
> 　　一个测试点内包含多组数据。  
> 　
> 
> ### Input ###
> 
> 　　第一行一个整数T\\(( T\\le 10 )\\)，表示数据组数  
> 　　第二行开始共T行，每行三个数n m p，意义如上  
> 　
> 
> ### Output ###
> 
> 　　共T行，每行一个整数表示答案。  
> 　
> 
> ### Sample Input ###
> 
> 　　2  
> 　　1 2 5  
> 　　2 1 5  
> 　
> 
> ### Sample Output ###
> 
> 　　3  
> 　　3  
>

#### **题目地址：　　[luoguP3807 【模板】卢卡斯定理][luoguP3807]** ####

#### **题目大意：** 题目已经很简洁了>\_< ####

#### **题解：** ####

> 　　**模板题**

--------------------

**AC代码**

#include <cstdio> 
    #define ll long long
    using namespace std;
    const int N=1e5+5;
    int Q,n,m,mo;
    ll fac[N],inv[N];
    ll C(int n,int m){
        if(n<m)return 0;
        if(n<mo)return ((fac[n]*inv[m])%mo*inv[n-m])%mo;
        return C(n/mo,m/mo)*C(n%mo,m%mo)%mo;
    }
    int main(){
        scanf("%d",&Q);
        while(Q--){
            scanf("%d%d%d",&n,&m,&mo);
            fac[0]=1;
            for(int i=1;i<=100000;i++)
                fac[i]=fac[i-1]*i%mo;
            inv[0]=1;inv[1]=1;
            for(int i=2;i<=mo-1;i++)inv[i]=(inv[mo%i]*(mo-mo/i))%mo;
            for(int i=1;i<=mo-1;i++)inv[i]=(inv[i]*inv[i-1])%mo;
            printf("%d\n",C(n+m,m));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/shaokele/p/9295143.html

[luoguP3807]: https://www.luogu.org/problemnew/show/P3807

发表评论取消回复

表情：

评论列表（有 0 条评论，266人围观）

还没有评论，来说两句吧...

相关阅读

相关每日一题:由卢卡斯队列引出java四舍五入

一.题目引出黄金分割数 0.6180.6180.618 与美学有重要的关系。舞台上报幕员所站的位置大约就是舞台宽度的 0.6180.6180.618 处，墙上的画像一般

「爱情、让人受尽委屈。」/ 2024年04月01日 14:16/ 0 赞/ 59 阅读

相关高等数学：高斯定理

文章目录一、前提条件二、高斯定律三、高斯定律应用一、前提条件 x = r s i n θ c o s ψ y = r s i n θ

╰半夏微凉°/ 2023年10月15日 11:18/ 0 赞/ 65 阅读

相关尼科彻斯定理

目录 1.题目概述 2.题解思路分析具体实现 -------------------- 1.题目概述 > 验证尼科彻斯定理，即：任何一个整数m的立方都可以

淡淡的烟草味﹌/ 2023年10月14日 17:36/ 0 赞/ 19 阅读

相关卢卡斯定理+特征方程

![20200728094219216.png][] 学校的每日一题首先先想出插板法将n个区域分为k份，每份奖品不同，这样就可以保证转动一格后每个板子处会奖品不同，然后问

本是古典何须时尚/ 2023年03月02日 05:30/ 0 赞/ 23 阅读

相关数论：Lucas（卢卡斯）定理

Lucas（卢卡斯）定理 Lucas定理：用来求 c(n,m) mod p，p是素数的值。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_s

女爷i/ 2023年01月13日 10:54/ 0 赞/ 276 阅读

相关 Polya定理模板

相信很多初学者刚接触Polya定理的时候一脸懵逼，因为它以许多离散数学的知识为基础，所以不太好上手，所以我在这里把模板贴出来。 Polya定理是用来求出m种颜色涂入n个对象一

比眉伴天荒/ 2022年06月11日 02:16/ 0 赞/ 156 阅读

相关 Lucas定理模板

Lucas定理是用来求解C(m,n)mod p的值的。其中m和n的值可以很大，p一定是素数。对阶乘打表的模板 LL quick_mod(LL a, LL b, L

女爷i/ 2022年06月09日 13:27/ 0 赞/ 188 阅读

相关卢卡斯定理

前言：可以用来计算 $C\_\{n\}^\{m\}\\%p$ 正文：卢卡斯定理卢卡斯定理适用于模数 $p$ 为质数的情况首先我们知道组合数的计算公

小灰灰/ 2021年12月16日 04:36/ 0 赞/ 360 阅读

相关 luoguP3806 【模板】点分治1

include<bits/stdc++.h> define setIO(s) freopen(s".in","r",stdin) define max

逃离我推掉我的手/ 2021年11月16日 05:26/ 0 赞/ 286 阅读

相关 luoguP3807 【模板】卢卡斯定理

www.cnblogs.com/shaokele/ -------------------- > luoguP3807 【模板】卢卡斯定理 > > 　　Time Li

﹏ヽ暗。殇╰゛Y/ 2021年09月29日 09:52/ 0 赞/ 267 阅读