组合数取余模板

亦凉 2022-05-29 22:51 175阅读 0赞

[【参考博文地址－感谢原博主分享模板】][Link 1]

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    LL mod_pow(LL x, LL n, LL p){
        LL res = 1;
        while(n){
            if(n & 1) res =res * x % p;
            x = x * x % p;
            n >>= 1;
        }
        return res;
    }
    
    LL comb(LL n, LL m, LL p){
        if(m > n) return 0;
        LL ret = 1;
        m = min(n - m, m);
        for(int i = 1; i <= m; i ++){
            LL a = (n + i - m) % p;
            LL b = i % p;
            ret = ret * (a * mod_pow(b, p - 2, p) % p) % p;
        }
        return ret;
    }
    
    LL Lucas(LL n, LL m, LL p){
        if(m == 0) return 1;
        return comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
    }
    
    int main(){
        int T;
        LL n, m, p;
        scanf("%d", &T);
        while(T--){
            scanf("%lld %lld %lld", &n, &m, &p);
            printf("%lld\n", Lucas(n, m, p));
        }
        return 0;
    }

[Link 1]: https://www.cnblogs.com/zyf0163/p/4838566.html

发表评论取消回复

表情：

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

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

相关阅读

相关 js取整数、取余数的方法

取整 1.取整 // 丢弃小数部分,保留整数部分 parseInt(5/2)　　// 2 2.向上取整 // 向上取整,有小数就整数

左手的ㄟ右手/ 2023年10月11日 11:43/ 0 赞/ 40 阅读

相关 java取余(java取余数的函数)

java 求余数用%就可以。 int i = 5; int j = 8; int z = 8 % 5; System.out.println("余数：" + z

Myth丶恋晨/ 2023年09月25日 08:37/ 0 赞/ 58 阅读

相关关于取余数的方法

代码 include<iostream> using namespace std; int main(){ int siz

偏执的太偏执、/ 2023年01月01日 01:50/ 0 赞/ 134 阅读

相关 js 除法取整数、取余数的方法

\\js 除法取整数、取余数的方法取整 1.取整 // 丢弃小数部分,保留整数部分 parseInt(5/2)　　// 2 2.向上取

布满荆棘的人生/ 2022年09月10日 06:16/ 0 赞/ 275 阅读

相关组合数取余模板

[【参考博文地址－感谢原博主分享模板】][Link 1] include <cstdio> include <cstring> include <al

亦凉/ 2022年05月29日 22:51/ 0 赞/ 176 阅读

相关大数取余模板

include<stdio.h> include<stdlib.h> include<string.h> int big(int BigNum[

悠悠/ 2022年05月17日 13:19/ 0 赞/ 173 阅读

相关递推求组合数模板

const LL MAX = (LL)1e15 + 100; const int MAX_INDEX = 1001; LL f[MAX_INDEX][M

柔光的暖阳◎/ 2022年05月14日 13:54/ 0 赞/ 194 阅读

相关 ecshop模板取模运算,取余运算符

比如模板中.文章列表中需要调用20个文章,要求每4个商品后面就增加一个换行符.可以这样写 {foreach from=get_advlist_by_id(6) ite

分手后的思念是犯贱/ 2021年09月25日 22:24/ 0 赞/ 432 阅读

相关组合数模板

证明过程可参考此篇博客[https://www.cnblogs.com/liziran/p/6804803.html][https_www.cnblogs.com_lizira

灰太狼/ 2021年07月16日 13:32/ 0 赞/ 385 阅读

相关 js取整数、取余数的方法

1.丢弃小数部分,保留整数部分 parseInt(5/2) 2.向上取整,有小数就整数部分加1 Math.ceil(5/2) 3,四舍五入. Math.roun...

朱雀/ 2021年03月16日 15:28/ 0 赞/ 560 阅读