首页 > 其他分享 >Lucas定理

Lucas定理

时间:2023-08-04 19:48:09浏览次数:44  
标签:pq return Lucas 定理 ans mod

Lucas定理:

主要是求$C_{n}^{m}$在模$p$情况下($mod \, p$)(一般$p$较小,而$n,m$较大的情况)

公式:

$ C_{n}^{m} ≡  C_{n \, mod \, p}^{m \, mod \, p} \times C_{n/p}^{m/p}  (mod \, p) $

证明以后补吧

就以这题来说明具体解法:

题目

Luogu P3807 【模板】卢卡斯定理/Lucas 定理

Code:

//From:201929
#include<bits/stdc++.h>
#define L long long
using namespace std;
L pq[100005];
L n,m,mod;
L quick(L x,L y)//快速幂
{
    L ans=1;
    while(y)
    {
        if(y%2) ans=(ans*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return ans;
}
L q(L x,L y)
{
    if(y>x) return 0;
    return (pq[x]*quick(pq[y],mod-2))%mod*quick(pq[x-y],mod-2)%mod;
    //pq[x]/pq[y]/pq[x-y]
    //逆元变成pq[x]*(pq[y]^(mod-2))*(pq[x-y]^(mod-2))
    //暴力求解C x,y的值
}
L lucas(L x,L y)
{
    if(y==0) return 1ll;
    return (lucas(x/mod,y/mod)*q(x%mod,y%mod))%mod;
}
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&mod);
        pq[0]=1;
        for(int i=1;i<=mod;i++) pq[i]=(pq[i-1]*i)%mod;
        //预处理小情况(x<mod)的答案
        printf("%lld\n",lucas(n+m,m));
    }
    return 0;
}

 

标签:pq,return,Lucas,定理,ans,mod
From: https://www.cnblogs.com/201929-whx/p/17606822.html

相关文章

  • 兰道定理
    定义竞赛图的比分序列是将竞赛图每个点的出度从小到大排列得到的序列。所谓兰道定理,即一个长度为\(n\)的序列\(\{s_i\},s_i\les_{i+1}\)是合法的比分序列当且仅当\(\forallk,\sum_{i=1}^ks_k\geC(k,2)\)进一步的一个竞赛图强连通的充要条件是:把它的所有顶点按照入度d从小到大......
  • 动量定理Forexclub总结的交易规则
    动量定理策略是一种趋势策略,基于周线图中的“三烛台”形态(上涨或下跌)进行交易。Forexclub总结的交易规则如下:1. 下一个烛台必须比上一个烛台大,以确认趋势存在。2. 多奇烛台(不带主体的烛台)不考虑在内。3. 止损设置在序列中第一根蜡烛线的收盘水平。4. 止盈是最后一个烛台的5......
  • 安培定理
    (1)设dF12为电流元1给电流元2的力,I1和I2分别为他们的电流强度,dl1和dl2分别为两线元的长度,r12为两电流元的距离,则dF12的大小满足下列比式:或 dF12的大小还与两电流元的取向有关。(2)电流强度单位(1)中dF12的单位为N=kg*m/s2,长度dl1、dl2和r12的单位为m,将系数k写成如下形式:取μ0数......
  • 中国剩余定理
    由【物不知数】问题引入:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?意思就是有一个数满足除以3余2,除以5余3,除以7余2。不过解法还挺公式化的,这里就用变量整理吧x=a1(modb1)x=a2(modb2)x=a3(modb3)M=b1*b2*b3,c1=M/b1=b2*b3,c2=M/b2=b1*b3,c3=M/b3=b1*b2求......
  • Burnside 定理
    Burnside定理问题:给定一个\(n\)个点,\(n\)条边的环,有\(m\)种颜色,给每个顶点染色,问有多少种本质不同的染色方案,答案对\(10^9+7\)取模注意本题的本质不同,定义为:只需要不能通过旋转与别的染色方案相同。题目初步解读我们考虑如果不要求本质不同只需要\(n^n\)。但因为......
  • 【模板】数论基础:exGCD,exCRT,inverse,Lucas,BSGS,primitive root
    7.29数论WIP\(a\equivb\pmodp\Rightarrow\frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{p}{d}},d=\gcd(a,b,p)\)。exGCD若\((a,b)=1\),则\(0\leqx<b\),\(ax\bmodb\)互不相同,有一个是\(1\)。证明:\(ax_1\equivax_2\pmodb\)则\((x_1-x_2)a|b\),因为......
  • 被主定理震撼到了
    分析复杂度时可能有用。(主定理狗都不学)若有递归式\(T(n)=aT(\dfrac{n}{b})+f(n)\)则分以下三种情况:\(f(n)=O(n^{\log_ba-\epsilon}),\epsilon>0\),此时\(T(n)=\Theta(n^{\log_ba})\)\(f(n)=\Theta(n^{\log_ba}\log^kn),k\geq0\),此时\(T(n)=\Theta(n^{\log_ba}\l......
  • 动量定理不愧是大师都在推荐使用的交易策略Forexclub总结两点
    动量定理对交易策略的重要性不言而喻,许多交易大师都在推荐使用。Forexclub认为它可以通过观察趋势的持续时间来预测价格走势,使用振荡器来确定趋势支点,这个振荡器比标准振荡器更快,能够提前给出买卖信号。该振荡器由两条线组成,信号线是虚线,附加线是实线。接收线有两种颜色,橙色和绿色......
  • 图论中的实用定理与结论
    结合图论中的概念与定义食用更佳。网络流与二分图Konig定理:最小点覆盖=最大匹配(proof)二分图最大独立集=点数-最大匹配二分图最大团=补图的最大独立集最大流=最小割二分图最小链覆盖数=最小边覆盖=节点数-最大匹配数有孤立点的二分图没有边覆盖Hall定......
  • 【模板】图的计数相关:行列式及求值、Matrix-Tree 定理、BEST 定理、LGV 引理
    归类为线性代数、图论。证明都是神仙,特别是名字带“理”的,不证了。行列式定义行列式(Determinant)是对\(n\)阶方阵\(A\)定义的,是一个标量。\(A\)的\(n\)阶行列式\(det(A)\)或\(|A|\)定义如下:\[det(A)=\sum_p(-1)^{\mu(p)}\prod_{i}A[i][p_i].\]这里将排列的逆序对数......