P3807 【模板】卢卡斯定理

题目背景

这是一道模板题。

题目描述

给定n,m,p( $1\le n,m,p\le 10^51≤n,m,p≤10?5??)$

求 $C_{n+m}^{m}\ mod\ pC?n+m?m?? mod p$

C表示组合数。

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

输入输出格式

输入格式：

第一行一个整数T( $T\le 10T≤10)，表示数据组数$

第二行开始共T行，每行三个数n m p，意义如上

输出格式：

共T行，每行一个整数表示答案。

输入输出样例

输入样例#1：

21 2 52 1 5

输出样例#1：

33



模板：

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 100001#define ll long longusing namespace std;ll t,n,m,p,ans,f[N];ll read(){    ll x=0,f=1; char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}    return x*f;}ll mi(ll n,ll k,ll p){    ll res=1;    while(k)    {        if(k&1)  res=n*res%p;        n=n*n%p; k>>=1;    }    return res;}ll c(ll n,ll m,ll p){    if(m>n) return  0;    return f[n]*mi(f[n-m]*f[m],p-2,p)%p;}ll lus(ll n,ll m,ll p){    if(m==0) return  1;    return c(n%p,m%p,p)*lus(n/p,m/p,p)%p;}int main(){    t=read();    while(t--)    {        f[0]=1;        n=read(),m=read(),p=read();        for(ll i=1;i<=p;i++)          f[i]=f[i-1]*i%p;        ans=lus(m+n,m,p);        printf("%d\n",ans);    }    return 0;}

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

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们