同余系基本定理2 更新于 2026/6/18 16:17:02 作者

command_block

我与同余系的第一次相逢，是在一个寒冷的冬日。

• 故事：

  彼时，本蒟蒻刚学会解一元一次方程还没超过半年(当然,按教科书进度算),然后作为垫名额选手参加了GDKOI。

  DAY1文件爆0，心态巨崩(误以为Trie树上匹配一次O(1)海星?)。

  DAY1.5听到大佬讲座，介绍了下“简单数论”。

  dalao:"啊这个模运算的性质你们都知道吧，就是%^&@#HTR^#"

  dalao:"啊这个EXGCD你们都知道吧，就是%^&@#HTR^#"

  dalao:"有同学想仔细了解吗？就是$\%\mu*!R@E\phi X$(手撕一波式子)"

  dalao:"……好的，我们开始讲$Lucas$定理"

  事后，我把EXgcd的代码背了下来，结果过了两天就忘了(汗

胡扯完毕，大家放轻松。

$\tiny \text{(2020.4.11) 两年天坑终于更完了!}$

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

1.同余系基本运算

• 同余系的定义

首先讲一下同余系的概念,对于第一次接触除了经典实数体系之外的同学,可能有点难理解。

大家习惯的是实数域 $?$ ,如果您告诉我您习惯 $?$ 您可以马上跳过这一节。

• 首先通俗简要地介绍一下群

  群由两个部分组成 : 元素域 + 运算 ( 群友 + 交互 )

  而且,群大多数时候要满足一个性质,即两个群内的元素,经过运算得到的结果也一定在群内。这叫做封闭性。

  比方说,自然数对加法和乘法是封闭的 : 任意两个自然数加,乘在一起仍然是自然数。

  我们一旦加入减法,这就产生了负数,我们的元素域要扩展到全体整数。

  一旦假如除法,就会出现分数,元素域扩展到了全体有理数。

  之后的代数数,实数,复数按下不表。

这个年代,有很多很多的计数题目,这类题目的答案往往是天文数字。

在遥远的过去,毒瘤出题人往往会要求选手写高精度来求出确切的答案,于是计数题一直没有普及。

直到同余系普及,计数题目便不再依赖大数计算,得以普及并迅速发展。于是就出现了新的毒瘤。

或许你曾见过计数题带有模数,如 P4017 最大食物链计数 , P5520 [yLOI2019] 青原樱 , P5888 传球游戏 等等。

做这种题的时候,一种容易想到的思路是 : 先求出确切答案,然后再取模。

当然这是相当搞笑的行为,如果你第一次见到对答案取模,去询问学长或者老师,他们多半会告诉你:

$$(a+b)\bmod p=(a\bmod p)+(b\bmod p)\bmod p$$ $$(a*b)\bmod p=((a\bmod p)*(b\bmod p))\bmod p$$

太过通俗,不证。

也就是说,涉及加法和乘法时,取模的顺序不会影响答案。

这启发我们建立同余系(模$p$意义下):

$\color{blue}\text{定义:}$

• 同余系加法 : $a$加$b=(a+b)\bmod p$

• 同余系乘法: $a$乘$b=(a*b)\bmod p$

  比如$2+3=1(\!\!\!\!\mod 4),2*3=2(\!\!\!\!\mod 4)$。

  不难发现,同余系只需要包含$0...(p-1)$这些整数就可以封闭了。

  减法也是类似的,不过由于不存在所谓“负数”,需要使用类似补码的概念。

这样,同余系中的数很小,就不需要涉及大数运算了。

当然同余系存在的理由并不止于计数题,它本身就是一个优美而深奥的世界,可以导出许多有用的结论。

那么,就让我们开始吧!

• 逆元引入

部分计数题目,只涉及加法和乘法,我们直接使用上面介绍的同余系就可以解决。

可能你会好奇 : 除法去哪了?这里都是整数,除出分数怎么办?

我们当时是怎么定义除法的呢?

根据除法是乘法的逆运算,我们要找到一个数,使得其能“抵消”乘法的影响,这就是倒数。

就是构造出$\frac{1}{a}$,使得$a*\frac{1}{a}=1$,然后乘以$\frac{1}{a}$这个操作就等价于除以$a$.

类似地,我们可以$\color{blue}\text{定义}$同余系内的乘法逆元(倒数)$a^{-1}$是 : 满足$ab=1\pmod p$的$b$

根据这个同余系的定义,这个$a^{-1}$是整数。没错,不是分数是整数。

这就是同余系的魅力了,无论在经典数系里面怎样的复杂,只要能在同余系中表示,就一定是整数。

$a^{-1}$满足和经典数系中$\frac{1}{a}$中类似的种种性质,就不再赘述了。

$a=0$时$a^{-1}$不存在,正如经典数系中不能除以$0$.

其他情况下,$a^{-1}$如果存在,则是唯一的。

$\color{blue}\text{证明:}$ 假设有$ax=1,ay=1$

则有:$xay=(xa)y=y$,同时有$xay=x(ay)=x$,所以有$x=y$.

这个逆元怎么求呢?可以暴力枚举$1...(p-1)$来尝试,复杂度$O(p)$.

显然这是很糟糕的复杂度,至于如何快速求解,后面再说。

现在四则运算都齐了,而且是封闭的,你可以像小学数学一样随意使用同余系了。

许多在实数系里面成立的东西在同余系里也成立,这里不再赘述了,请读者自行探究。

• 附送一些简单的关于模的式子:

  设$\lfloor x\rfloor$为$x$向下取整的结果。,如$\lfloor 2.33\rfloor=2$

  有$a \bmod b=a-b\lfloor a/b\rfloor$

• 逆元的各种求解方法

• 费马小定理

这里要求模数$p$是素数,由于素数有很多良好的性质,一般题目取模都是用素数,这个定理应用也最广泛。

• $\color{blue}\text{定理:}$ 在模素数$p$的同余系下,任意正数

  $$\large a^{p-1}=1\pmod p$$

那么,$a^{-1}=a^{p-2}$,写个快速幂就能够求逆元了。

• $\color{blue}\text{证明:}$

  默认$p$为质数。

  • 引理1:

    当$p$为质数且$c$为整数,由$ac=bc\pmod p$可推出$a=b\pmod p$

    $ac=bc\pmod p→ac-bc=0\pmod p→c(a-b)=0\pmod p$

    所以$c(a-b)$是$p$的整数倍。

    因为$p$为素数,所以$c,p$互质,即$(a-b)$是$p$的整数倍。

    即$a-b=0\pmod p→a=b\pmod p$,证毕。

  取集合$T_1\{1,2,3,...,p-1\}$这$p-1$个数,他们的积为$(p-1)!$

  然后,将$\{1,2,3,...,p-1\}$同乘$a$,其中$a$是一个正整数($p$的同余系下)

  得集合$T_2\{a,2a,3a,...,(p-1)a\}$

  • 假设这些数中有两个相同:

    得$k_1a=k_2a\pmod p$,其中$k_1,k_2∈T_1$且$k_1≠k_2$。

    然而根据引理1,$k_1=k_2$,矛盾,假设不成立,即这些数各不相同。

  • 假设这些数中有某个为0:

    得$ka=0\pmod p$,其中$k,a$不为0.

    由假设得$ka$是$p$的整数倍。

    然而$k,a$都和$p$互质,矛盾,假设不成立。

  故集合$T_2$中的数各不相同,且不为0,那么$T_2=T_1=\{1,2,3,...,p-1\}$

  我们把$t_2$里面的所有数乘在一起,得到$a^{p-1}*(p-1)!$

  因为集合$T_1=T_2$所以对应积相等,即$a^{p-1}*(p-1)!=(p-1)!\pmod p$

  因为$(p-1)!$与$p$互质,所以$a^{p-1}=1\pmod p$,证毕。

求逆元快速幂合一代码:

ll powM(ll a,int t=mod-2)
{
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}

• 斐蜀定理

遗憾的是,逆元并非像实数系中那样总是存在,来看一下其存在的条件。

• $\color{blue}\text{定理:}$ $ax+by=c$有解$\{x,y\}$当且仅当$c$是$\gcd(a,b)$的倍数。

• $\color{blue}\text{证明:}$ (这里只证明必要性)采用反证法。假设$c$不是$\gcd(a,b)$的倍数。

  设$d=\gcd(a,b)$,将等式两边除以$d$可得 : $a\frac{x}{d}+b\frac{y}{d}=\frac{c}{d}$

  根据最大公因数的定义,式子左边是整数。而由于$c$不是$d$的倍数,右边不是整数,矛盾。

这玩意和逆元有什么关系呢?

注意到,当$\gcd(a,b)=1$的时候,方程变为$ax+by=1$

$ax+by=1$等式两边模b得到 : $ax=1\pmod p$

这正是逆元的定义式!

而且根据斐蜀定理，$gcd(a,b)>1$时这个方程无解。

否则$gcd(a,b)=1$,此时求出的$x$就是$a^{-1}$

• $\color{blue}\text{推论:}$ $ax=1\pmod p$ 有解当且仅当 $a$ 与 $p$ 互质(也记作$a\perp b$)

斐蜀定理还可以扩展到更多元的情况 : P4549 【模板】裴蜀定理

• EXgcd

P1082 同余方程 (注意模数不一定是质数)

EXgcd,即扩展欧几里得算法。

可以求出 $ax+by=\gcd(a,b)$ 的一组解。(其中a,b已知)

这个东西的实现类似于数学中的归纳法，对初学者来说有些难理解。

$\large{ax+by=\gcd(a,b)}$

我们设$a_2=b;\ b_2=a\%b$

根据普通欧几里得算法可以得到$gcd(a,b)=gcd(a_2,b_2)$

假设我们知道 $\large{a_2x+b_2y=gcd(a,b)}$ 的解 $\large{x_2,y_2}$ 。

把$a_2=b;\ b_2=a\%b$代入回去。

得到$bx_2+(a\%b)y_2=\gcd(a,b)$

$bx_2+(a-b\left\lfloor{a/b}\right\rfloor)y_2=\gcd(a,b)$

$bx_2+ay_2-b\left\lfloor{a/b}\right\rfloor{y_2}=\gcd(a,b)$

$ay_2-b(x_2-\left\lfloor{a/b}\right\rfloor{y_2})=\gcd(a,b)$(类似主元法)

比对 $ax+by=\gcd(a,b)$

得到 $x=y_2;y=x_2-\left\lfloor{a/b}\right\rfloor{y_2}$

也就是说我们知道$a_2x+b_2y=\gcd(b,a\%b)$的解之后可以$O(1)$推导出$ax+by=\gcd(a,b)$的解。

这是个嵌套的形式，对于$a_2x+b_2y=\gcd(b,a\%b)$，我们也转化一下，再转化，还转化……

但是这并不会无限的进行下去。$b==0$时,根据普通欧几里得算法，得到$gcd(a,0)=a$

得 $ax=a$，直接令$x=1;y=0$即为一组合法解。

这样的话，就能解上一个方程，上上个，上上上个也迎刃而解。

很明显，EXgcd的复杂度与普通的欧几里得算法相同，均为$O(\log a)$

我们来手玩一下加深印象。

求出 ${7x+3y=gcd(3,7)}$ 的一组解

• 变一下得到 ${3x_2+y_2=1}$

  • 再变一下得到 ${x_3=1}$

    得到 $x_3=1;y_3=0$

  回顾前文：$x=y_2;y=x_2-\left\lfloor{a/b}\right\rfloor{y_2}$

  得到 $x_2=0;y_2=1$

最终得到 $x=1;y=-2$

带入${7x+3y=gcd(3,7)}$得到${7*1+3*(-2)=1}$,一切正常。

代码实现: 请仔细查看引用关系。

void exgcd(ll a,ll b,ll &x,ll &y)
{
  if (a==1&&b==0)
    {x=1;y=0;return ;}
  exgcd(b,a%b,y,x);
  y-=x*(a/b);
}

那么问题来了，这个东西和逆元有啥关系？

根据上文的推理,当$\gcd(a,p)=1$时,我们得到的$x$即为所求的逆元。

Exgcd并不基于同余系,所以可能求出来负数,模一下变成正数就好。

P5656 【模板】二元一次不定方程(exgcd)

这个毒瘤模板还要求给出最大最小解以及解的个数……可以加深对这个算法的理解。

我们的扩展欧几里得只能够处理$ax+by=\gcd(a,b)$的情况,而现在要求解$ax+by=c$的一般情况。

根据斐蜀定理,必须要满足$c$是$d=\gcd(a,b)$的倍数,否则无解。

我们令$a'=a/d,b'=b/d$,则有$\gcd(a',b')=1$,这就是我们的经典逆元方程$a'x'+b'y'=1$了。

直接扩欧之后,特解$x_*,y_*$之后,通解则是$\begin{cases}x_t=x_*+tb'\\y_t=y_*-ta'\end{cases}$

充分性是容易验证的,至于必要性,不证。

将一组 $x,y$ 分别乘上 $c/d$ 即可得到原方程的一组解$ax_*+by_*=c$。

其最小正整数解是容易求的,直接取模意义下的解即可。根据相应的等式可求得另一个元。

容易发现$x$变小时$y$增大,则$x$取最小正整数解时$y$是最大解,反之亦然。

可以据此判定有没有正整数解。注意可能模出0,这也是题意不自然的地方。

解的数量就是$\dfrac{x_{\max}-x_{\min}}{b}+1$。

#include<cstdio>
#define ll long long
#define pf printf
using namespace std;
inline int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int gcd(int a,int b)
{return !b ? a : gcd(b,a%b);}
void exgcd(ll a,ll b,ll &x,ll &y)
{
  if (b==0){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=x*(a/b);
}
int T;
ll a,b,c,d,x,y;
int main()
{
  int T=read();
  for (int i=1;i<=T;i++){
    a=read();b=read();c=read();
    d=gcd(a,b);a/=d;b/=d;
    if (c%d){puts("-1");continue;}
    exgcd(a,b,x,y);
    x*=c/d;y*=c/d;
    ll xl,xr,yl,yr;
    xl=(x%b+b)%b;if (!xl)xl=b;
    yr=(c-a*d*xl)/(b*d);
    yl=(y%a+a)%a;if (!yl)yl=a;
    xr=(c-b*d*yl)/(a*d);
    if (yr<=0){
      pf("%lld %lld\n",xl,yl);
    }else 
      pf("%lld %lld %lld %lld %lld\n",(xr-xl)/b+1,xl,yl,xr,yr);
  }return 0;
}

• 例题 P3986 斐波那契数列

  教练说选手必须要有脑子,我就来找脑子了。

  题意 : 有如下数列 : $G[0]=a;\ G[1]=b;\ G[n]=G[n-1]+G[n-2](n>1)$

  给出一个$k$,询问有多少对正整数$(a,b)$使得$k$在$G[2...∞]$中出现。

  $k\leq 10^9$,答案对$10^9+7$取模。

---

首先,这是对答案取模,而非对数列取模,看错题可能导致您神游到三里屯去。

众所周知,斐波那契数列的增长速度是指数级的,我们只需要考虑前$O(\log k)$项即可。

设$F[n]$为斐波那契数列。

然后根据递推(转移矩阵)的结合律,能得到$G[n]=a*F[n-1]+b*F[n-2]$.

然后针对每一位,能得到形如$F[n-1]x+F[n-2]y=k$的不定方程。

而$k$不可能在数列中出现两次,每个位置的解没有交集,所以直接讲每个位置的方程的解的个数加起来即可。

似乎还是没有用到脑子,怎么办啊……

#include<cstdio>
#define ll long long
#define pf printf
using namespace std;
int gcd(int a,int b)
{return !b ? a : gcd(b,a%b);}
void exgcd(ll a,ll b,ll &x,ll &y)
{
  if (b==0){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=x*(a/b);
}
int T;
ll calc(ll a,ll b,ll c)
{
  ll d=gcd(a,b),x,y;a/=d;b/=d;
  if (c%d)return 0;
  exgcd(a,b,x,y);
  x*=c/d;y*=c/d;
  ll xl,xr,yl,yr;
  xl=(x%b+b)%b;if (!xl)xl=b;
  yr=(c-a*d*xl)/(b*d);
  if (yr<0)return 0;
  yl=(y%a+a)%a;if (!yl)yl=a;
  xr=(c-b*d*yl)/(a*d);
  return (xr-xl)/b+1;
}
ll k,F[105];
int main()
{
  scanf("%lld",&k);
  F[0]=F[1]=1;
  ll ans=0;
  for (int i=2;F[i-1]+F[i-2]<=k;i++){
    F[i]=F[i-1]+F[i-2];
    ans=(ans+calc(F[i-1],F[i-2],k))%1000000007;
  }printf("%lld\n",ans);
  return 0;
}

• 欧拉定理

这部分需要一定的附加知识,看不懂建议跳过。

有的时候模数不一定是质数,这时候就要用到欧拉定理。这是费马小定理的扩展。

• $\color{blue}\text{定理:}$ 在模$m$的同余系下,当$x\perp m$时,有

$$x^{\varphi(m)}=1\pmod m$$

其中$\varphi(m)=\sum\limits_{i=1}^m[i\perp m]$,是欧拉函数。

证明和费马小定理类似,考虑构造与 $m$ 互质的数的集合 $S$,易得$|S|=\varphi(m)$.

将每个数乘上$x$得到新集合 $S'$,由于 $x\perp m$,所得 $S'$ 内的元素每个仍然与$m$互质,所以和原来的集合$S$相同。

考虑两个集合的乘积,设 $S$ 内元素的乘积为 $c$,则 $S'$ 内元素乘积为 $cx^{\varphi(m)}$,则有$c=cx^{\varphi(m)}\pmod m$

由于$c\perp m$,方程两边可以消去$c$,就得到$x^{\varphi(m)}=1\pmod m$

令$m=p$可得$\varphi(p)=p-1$,即$x^{p-1}=1\pmod p$,正是费马小定理。

可以用于求逆元 : $x^{\varphi(m)-1}=x^{-1}\pmod m$,但是真正的用处是降幂,这会在后续文章中讲到。

• 线性求[1,n]逆元

P3811 【模板】乘法逆元

我们要预处理出$[1,n]$的逆元$\pmod p$(质数),直接使用上述的某一种方法大力求，复杂度为$O(nlogn)$。

下面介绍一些复杂度为$O(n)$的算法。

• 方法一 : 整除拆分并推式子

  假设我们已经求出了$[1,n-1]$的逆元，现在要求$n^{-1}$

  设 $t=\lfloor p/n\rfloor,k=p\%n$;

  得$t*n+k=0 \pmod p$

  即$-t*n=k \pmod p$

  两边同时乘以$(n*k)^{-1}$

  得到$-t*k^{-1}=n^{-1} \pmod p$

  代回去，得到$n^{-1}=(p-p/n)*(p\%i)^{-1}\pmod p$

  由于$p\%i<i$所以$(p\%i)^{-1}$一定已经求出。

  边界就是$1^{-1}=1$。

int inv[MaxN];
void Init()
{
  inv[1]=1;
  for (int i=2;i<=n;i++)
  	inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}

• 方法二 : 造阶乘

  设$fac[n]=n!\pmod p,ifac[n]=(n!)^{-1}\pmod p$

  则$n^{-1}=\dfrac{(n-1)!}{n!}=fac[n-1]*ifac[n]$

  有 $\begin{cases}n!=(n-1)!*n \\ \dfrac{1}{n!}=\dfrac{1}{(n+1)!}*(n+1)\end{cases}$

  $O(n)$递推求解即可,更多时候用于$\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}$求组合数。

ll fac[MaxN],ifac[MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init()
{
  fac[0]=1;
  for (int i=1;i<=n;i++)
    fac[i]=fac[i-1]*i%mod;
  ifac[n]=inv(fac[n]);
  for (int i=n;i;i--)
    ifac[i-1]=ifac[i]*i%mod;
}

一道比较模板的题目 : P1641 [SCOI2010]生成字符串

• 真·线性求逆元

P5431 【模板】乘法逆元2

保证模数为质数。

观察造阶乘法的核心思想 : $n^{-1}=\dfrac{(n-1)!}{n!}=fac[n-1]*ifac[n]$

实际上是前缀逆乘上前缀积罢了。

考虑维护前缀积$s[n]$和前缀逆$inv[n]$,方法同上。

然后使用$(a[n])^{-1}=inv[n]*s[n-1]$即可。

复杂度是$O(n+\log p)$的,在某些时候能派上用场。

注意实际应用中,如果有$0$出现需要特判。

#include<cstdio>
#define ll long long
#define MaxN 5000500
using namespace std;
inline int read(){
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int mod;
ll powM(ll a,int t=mod-2)
{
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
ll inv[MaxN],s[MaxN],k;
int n,a[MaxN];
int main()
{
  scanf("%d%d%lld",&n,&mod,&k);
  s[0]=1;
  for (int i=1;i<=n;i++)
    s[i]=s[i-1]*(a[i]=read())%mod;
  inv[n]=powM(s[n]);
  for (int i=n;i;i--)
    inv[i-1]=inv[i]*a[i]%mod;
  ll ans=0,buf=1;
  for (int i=1;i<=n;i++){
  	buf=buf*k%mod;
  	ans=(ans+buf*inv[i]%mod*s[i-1])%mod;
  }printf("%lld",ans);
  return 0;
}

上回请看 同余系基本定理1

默认大家已经对同余系有一定的了解,而且能够熟练运用基础算法。

• P1495 【模板】中国剩余定理(CRT)

有若干个同余方程$\begin{cases}x=c_1\pmod {p_1}\\x=c_2\pmod {p_2}\\...\\x=c_m\pmod {p_m}\end{cases}$

满足$p_{1...m}$两两互质,求$x$的最小正整数解。

考虑把这些方程两两合并。

先看两个方程$\begin{cases}x=c_1\pmod{p_1}\\x=c_2\pmod {p_2}\end{cases}$

可以构造$x=c_1p_2+c_2p_1$,这样在模$p_1$时显出$c_1p_2$,模$p_2$时显出$c_2p_1$.

问题在于,我们希望得到$c_1$而非$c_1p_2$。这好办,再乘上$p_2$在模$p_1$时的逆即可。

合并完之后的模数是$p_1p_2$,由于互质所以总能求逆。

边界方程可以视作$x=0\pmod 1$.

复杂度$O(m\log p)$.

#include<cstdio>
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &x,ll &y){
  if (b==0){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=(a/b)*x;
}
ll inv(ll a,ll m){
  ll x,y;exgcd(a,m,x,y);
  return (x%m+m)%m;
}
int n;
ll c,p,ret,mp;
int main()
{
  scanf("%d",&n);
  ret=0;mp=1;
  for (int i=1;i<=n;i++){
    scanf("%lld%lld",&p,&c);
    ll sp=mp*p;
    ret=(ret*inv(p,mp)%sp*p+mp*inv(mp,p)%sp*c)%sp;
    mp=sp;
  }printf("%lld",ret);
  return 0;
}

• 例题 : P3868 [TJOI2009]猜数字

• P3807 【模板】卢卡斯定理

$\color{blue}\text{定理:}$ 当$p$是素数时

$$\dbinom{n}{m}\bmod p=\dbinom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\dbinom{n\bmod p}{m\bmod p}\bmod p$$

$\color{blue}\text{证明:}$ (可不掌握)

注意到$[x^m](1+x)^n=\dbinom{n}{m}$

构造$(1+x)^p=1+\binom{p}{1}x+\binom{p}{2}x+...+\binom{p}{p}x^p$

• 对于$1\leq i\leq p-1$,总有$\binom{p}{i}=0\pmod p$.

  原因是$\dbinom{p}{i}=\dfrac{p!}{(p-i)!i!}$,而$p$是素数,所以 $(p-i)!$ 和 $i!$ 都不含因子$p$,无法抵消$p!$中的恰一个因子$p$.

那么可以得到$(1+x)^p=1+x^p\pmod p$

能进一步推出$(1+x)^{p^k}=(1+x^p)^{p^{k-1}}=...=1+x^{p^k}$

我们把$n,m$都表示成两个p进制数,即$\begin{cases}n=\sum\limits_{i=0}a_ip^i\\m=\sum\limits_{i=0}b_ip^i\end{cases}$

然后考虑$(1+x)^n=\prod\limits_{i=0}(1+x)^{a_ip^i}$

$(1+x)^n=\prod\limits_{i=0}(1+x^{p^k})^{a^i}\pmod p$

提取第$m$项系数。

$[x^m](1+x)^n=[x^m]\prod\limits_{i=0}(1+x^{p^k})^{a^i}\pmod p$

由于乘积项的次数不交,可以把$m$分解。

“不交”的意思是某两位之间不会互相影响。因为将一个 $p$ 进制数的后 $n$ 位加起来之后肯定不足第 $n+1$ 位的一个 $1$ 大。

$\dbinom{n}{m}=\prod\limits_{i=0}[x^{b_ip^k}](1+x^{p^k})^{a^i}\pmod p$

$\dbinom{n}{m}=\prod\limits_{i=0}[x^{b_i}](1+x)^{a^i}\pmod p$

$\dbinom{n}{m}=\prod\limits_{i=0}\dbinom{a_i}{b_i}\pmod p$

即 : 把 $n,m$ 按照 $p$ 进制拆位,每一位对应求组合数乘积即可。

#include<cstdio>
#define MaxN 100500
#define ll long long
using namespace std;
int mod;
ll powM(ll a,int t=mod-2){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
ll fac[MaxN],ifac[MaxN];
ll sC(int n,int m){
  if (n<m)return 0;
  return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
ll C(ll n,ll m){
  if (!m)return 1;
  return sC(n%mod,m%mod)*C(n/mod,m/mod)%mod;
}
void Init()
{
  fac[0]=1;
  for (int i=1;i<mod;i++)
    fac[i]=fac[i-1]*i%mod;
  ifac[mod-1]=powM(fac[mod-1]);
  for (int i=mod-1;i;i--)
    ifac[i-1]=ifac[i]*i%mod;
}
void solve()
{
  ll n,m;
  scanf("%lld%lld%d",&n,&m,&mod);
  m+=n;Init();
  printf("%lld\n",C(m,n));
}
int main()
{
  int T;scanf("%d",&T);
  while(T--)solve();
  return 0;
}

• 例题 P4345 [SHOI2015]超能粒子炮·改

  题意 : 多次给出 $n,k$ ,求 $\sum\limits_{i=0}^k\dbinom{n}{i}\pmod {2333}$

  $T\leq 10^5;n,k\leq 10^{18}$,时限$\texttt{1s}$.

设 $p=2333$ ,显然这是个素数。

根据卢卡斯定理有 $\dbinom{n}{m}=\dbinom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\dbinom{n\bmod p}{m\bmod p}$

$ANS=\sum\limits_{i=0}^k\dbinom{n}{i}$

$=\sum\limits_{i=0}^k\dbinom{\lfloor n/p\rfloor}{\lfloor i/p\rfloor}\dbinom{n\bmod p}{i\bmod p}$

前半部分是块状变化的,我们分别枚举$\lfloor i/p\rfloor$ 和 $i\bmod p$。注意最后多出来的一个散块。

$=\sum\limits_{i=0}^{\lfloor k/p\rfloor-1}\dbinom{\lfloor n/p\rfloor}{i}\sum\limits_{j=0}^{p-1}\dbinom{n\bmod p}{j}+\dbinom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}\sum\limits_{j=0}^{k\bmod p}\dbinom{n\bmod p}{j}$

注意到$\sum\limits_{i=0}^{\lfloor k/p\rfloor-1}\dbinom{\lfloor n/p\rfloor}{i},\quad\sum\limits_{j=0}^{p-1}\dbinom{n\bmod p}{j},\quad\sum\limits_{j=0}^{k\bmod p}\dbinom{n\bmod p}{j}$均是子问题。

设 $f(n,k)=\sum\limits_{i=0}^k\dbinom{n}{i}$

则有 $f(n,k)=f(\lfloor n/p\rfloor,\lfloor n/k\rfloor-1)f(n\bmod p,p-1)+\dbinom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}f(n\bmod p,k\bmod p)$

先预处理 $p\times p$ 的 $f$,这用组合数递推不难做到 $O(p^2)$.

然后就是求解 $\dbinom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}$ ,使用Lucas定理即可做到 $O(\log_p n)$

观察参数 $n$ 的变化 : 不断除以 $p$。

然后由于 $f(n,k)$ 在 $k>n$ 时等于 $f(n,n)$ ,当 $n\leq p$ 时就已经达到边界,只需要递归 $O(\log_p n)$ 次。

复杂度$O(T\log_p^2n+p^2)$.

提交记录

• 周边 : Kummer定理

$\color{blue}\text{定理:}$ $\dbinom{n+m}{m}$ 中素因子 $p$ 的个数 $=n,m$ 在 $p$ 进制下做加法的进位次数。

注意到 $n!$ 中 $p$ 的次数是 $\sum\limits_{i=0}\lfloor n/p^i\rfloor$ ,证明比较显然。

根据 $\dbinom{n+m}{m}=\dfrac{(n+m)!}{n!m!}$

则因子 $p$ 的个数是 $\sum\limits_{i=0}\lfloor (n+m)/p^i\rfloor-\lfloor n/p^i\rfloor-\lfloor m/p^i\rfloor$

当某一位上 $\lfloor n/p^i\rfloor$ 相当于在 $p$ 进制表示下去掉后 $i$ 位。

那么只有 $n+m$ 在这里进位了才能逃脱被去掉的命运而恰好多$1$.

• 例题 : CF582D Number of Binominal Coefficients

  题意 : 给出参数 $lim,p,a$ ,求有多少个组合数 $\dbinom{n}{k}$ 是 $p^a$ 的倍数,且 $0\leq k \leq n \leq lim$.

  $p,a\leq 10^9,lim\leq 10^{1000}$,答案对$10^9+7$取模 ,时限$\texttt{4s}$.

根据 Kummer 定理,能将问题转化成这样的形式:

求两个数 $x,y$ 使得 $x+y\leq lim$ ,而且会在 $p$ 进制下产生多于 $a$ 个进位。

这看起来就很数位DP的样子。

设$f[i][j][0/1][0/1]$表示考虑了前$i$位,还需要产生$j$个进位,是否卡上界,这一位是否进位。

注意这里是不需要记录前导 $0$ 的,而且由于进位会影响上一位,还要钦定是否进位。

转移的时候分几类讨论 : (下一位进/不进位)(这一位进/不进位),分别计算可能的数对个数即可。

复杂度$O(\log^2lim)$

• 中段综合测试 : P2480 [SDOI2010]古代猪文

  题意 : 给出$n,g$,求$g^{\small\sum\limits_{k|n}\binom{n}{k}}$,对$999911659$取模。

  $n,g\leq 10^9$,时限$\texttt{1s}$.

首先,模数是个质数,根据费马小定理,指数要对 $mod-1$ 取模。

则对 $999911658=2\times 3\times 4679\times 35617$ 取模。

观察到没有重复的素因子,这比较和善。

求出分别模 $2,3,4679,35617$ 的结果,然后使用中国剩余定理合并即可(甚至不需要Exgcd)。

求组合数可以使用Lucas定理。

复杂度是$O(d(n)\log p+T(2+3+4679+35617))$

• 扩展欧拉定理(降幂塔)

上集我们已经证明了 : $[a\perp m]\ \Longrightarrow\ a^{\varphi(m)}=1\pmod m$

现在我们来看扩展形式, $\color{blue}\text{定理:}$

$$a^n=\begin{cases}a^{n\bmod\varphi(m)}&(a\perp m)\\a^n&(a\not\perp m,\ n< \varphi(m))\\a^{(n\bmod \varphi(m))+\varphi(m)}&(a\not\perp m,\ n\geq\varphi(m))\end{cases}\large\pmod m$$

第一种情况已被证明,第二种情况是显然的,现在我们来证明第三种情况。

说人话就是 : 当 $a\not\perp m$ 时,第一个 $\varphi(m)$ 不是循环,从第二个才开始进入。

不妨先考虑 $a=p^k$ 的情况。

此时若有 $p\not\perp m$ ,则 $m$ 可以表示成 $s*p^c$ ,且 $s\perp p$。

那么根据普通欧拉定理有 $p^{\varphi(s)}=1\pmod s$ 。 同时,由于 $\varphi$ 函数的积性,有 $\varphi(s)|\varphi(m)$。

于是有 $p^{\varphi(m)}=1\pmod s$

两边同时乘以 $p^c$ ,能够得到 $p^{\varphi(m)+c}=p^c\pmod {m}$

注意到 $\varphi(m)\geq \varphi(p^c)\geq p^{c-1}(p-1)\geq c$

所以有 $p^c=p^{c+\varphi(m)}=p^{c\bmod\varphi(m)+\varphi(m)}\pmod m$ ,我们证明了对于 $p^c$ 满足结论。

结论同时也对于 $p^{kc}$ 成立,可以归纳证明。

若有 $2c\geq n\geq \varphi(m) \geq c$ ,能推知 $n-c\leq \varphi(m)$

则 $p^n=p^{c}p^{n-c}=p^{c\bmod\varphi(m)+\varphi(m)+(n-c)\bmod\varphi(m)}$

有可能会出现 $c|n$ ,此时已经证毕。否则有 $c\bmod\varphi(m)+(n-c)\bmod\varphi(m)=n\bmod\varphi(m)$

然后对 $n$ 的上界归纳即可。

现在我们对任意的 $p^n$ 证明了 $p^n=p^{(n\bmod\varphi(m))+\varphi(m)}$

然后使用唯一分解定理即可把结论扩展至全体正整数。

• 例题 : P4139 上帝与集合的正确用法

  题意 : 求 $2^{2^{2^{2^{\dots}}}}\bmod m$ , $\ p\leq 10^7$

设$G(p)=2^{2^{2^{2^{\dots}}}}\bmod m$

根据扩展欧拉定理能得到 $G(p)=2^{G(\varphi(p))+\varphi(p)}$

边界就是 $2^{2^{2^{2^{\dots}}}}\bmod 1=0$

取多少次 $\varphi(p)$ 会得到 $1$ 呢?

注意到欧拉函数的其中一个定义式 : $\varphi(m)=m\prod\limits_{p|m}\frac{p-1}{p}$

当 $m$ 无素因子 $2$ 时,一个奇素因子一定会产生因子 $2$ ,因为 $p-1$ 是偶数。

当 $m$ 有素因子 $2$ 时,值至少减半。

综上,经过 $O(\log p)$ 次递归就能得到 $1$。

线性筛出欧拉函数复杂度是 $O(p+T\log^2p)$ 的。

提交记录

• 附加题 :

  • P4861 按钮

    若 $\gcd(k,m)>1$ ,显然无解。

    否则满足经典欧拉定理,则有 $k^{\varphi(m)}=1\pmod m$ ,但是 $\varphi(m)$ 并不是答案,可能存在更小的循环节。

    可能的循环节一定是 $\varphi(m)$ 的约数,否则能导出矛盾。

    于是只需要判定 $\varphi(m)$ 的约数即可,复杂度为 $O(\sqrt{m}\log m)$。

    [提交记录] ()

  • P3934 Nephren Ruq Insania

    考虑乘方降幂塔,在 $O(\log p)$ 层之后模数就会变为 $1$,所以我们只需要暴力取出 $l$ 后的若干项即可。

    上一题中,由于 $2^{2^{2^{2^{\dots}}}}$ 恒大于 $\varphi(m)$ ,所以总可以使用第三种情况。

    现在由于可能产生第二种情况,我们计算时需要按照如下原则:

    如果算的的数大于 $m$ 则替换成 $(a\bmod m)+m$,否则不变。

    提交记录

  • CF906D Power Tower : 上一题的静态版,但数据较强。

  • P3747 [六省联考2017]相逢是问候

    仍然考虑结论 : 降幂塔不超过 $O(\log p)$ 层。某个位置被赋值 $O(\log p)$ 次之后就必然变为 $c^{c^{c^{\dots}}}\bmod p$。

    考虑把不再变化的一整个区间冻结,可以证明只会产生 $O(n\log p)$ 次修改叶子的操作。

    每次单点修改需要计算一次降幂塔,朴素实现复杂度是$O(\log p^2)$的,无法通过。

    模数只有 $O(\log p)$ 个,可以分别于处理 $c$ 的光速幂。

    总复杂度为$O(\sqrt{p}\log p+m\log ^2p)$。

    提交记录

  • P5240 Derivation

• P4777 【模板】扩展中国剩余定理（EXCRT）

仍然是若干个方程组$\begin{cases}x=c_1\pmod {p_1}\\x=c_2\pmod {p_2}\\...\\x=c_m\pmod {p_m}\end{cases}$

求$x$的最小解,但不保证$p_{1...m}$互质。

仍然考虑两两合并$\begin{cases}x=c_1\pmod{p_1}\\x=c_2\pmod {p_2}\end{cases}$

原先我们要直接构造某个模数在另一个模数下的逆,现在似乎不太行了。

第一个方程的通解为$c_1+kp_1$,现在就是求一个 $k$ 使得$c_1+kp_1=c_2\pmod{p_2}$

移项有$kp_1=c_2-c_1\pmod{p_2}$,熟练的同学已经知道怎么做了。

等价于$kp_1+yp_2=c_2-c_1$

根据斐蜀定理,方程有解的充要条件是$\gcd(p_1,p_2)|(c_2-c_1)$.

如果可解,先扩欧求出$kp_1+yp_2=\gcd(p_1,p_2)$,然后乘以$\dfrac{c_2-c_1}{\gcd(p_1,p_2)}$即可。

注意,新的模数是$lcm(p_1,p_2)$。此外还要注意防止溢出。

复杂度仍然是$O(m\log p)$.

#include<cstdio>
#define ll long long
using namespace std;
inline ll mul(ll a,ll b,ll m){
  ll d=((long double)a/m*b+0.5);
  ll r=a*b-d*m;
  return r<0?r+m:r;
}
ll gcd(ll a,ll b)
{return !b ? a : gcd(b,a%b);}
void exgcd(ll a,ll b,ll &x,ll &y){
  if (b==0){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=(a/b)*x;
}
int n;
ll c1,p1,c2,p2;
int main()
{
  scanf("%d",&n);
  c1=0;p1=1;
  for (int i=1;i<=n;i++){
    scanf("%lld%lld",&p2,&c2);
    ll pd=gcd(p1,p2),sp=p2/pd*p1,k,y;
    c2=(c2-c1%p2+p2)%p2;
    //if (c2%pd) No Sol;
    exgcd(p1,p2,k,y);
    k=mul(k,(c2/pd),p2);
    c1=(c1+mul(p1,k,sp))%sp;
    p1=sp;
  }printf("%lld",c1);
  return 0;
}

• 例题 : P4774 [NOI2018]屠龙勇士

发现不会做这道题是写本文的动力之一。

首先容易发现,屠龙的规则和顺序严格确定,那么如果我们能成功,每一轮使用的剑是相同的。拿multiset维护一下便可。

设杀第$i$条龙的剑攻击力为$k_i$.

击杀每条龙的条件很像取模,我们能列出式子$k_ix=a_i\pmod {p_i}$

问题在于,可能有$a_i>p_i$,此时可能在比$0$大但为$p_i$倍数的血量停下来,所以$x$满足上述方程并不是充要条件。

考虑对每条龙记录砍到负数的最小次数的最大值,最后$x$在通解中取大一点就好了。

接下来的问题就是解方程组$\begin{cases}k_1x=c_1\pmod {p_1}\\k_2x=c_2\pmod {p_2}\\...\\k_mx=c_m\pmod {p_m}\end{cases}$

考虑将$kx=c\pmod p$变为形如$x=c\pmod p$的经典形式。

先特判$0$ : 当$p|k$且$p|c$时方程恒成立,不考虑。当$p|k$但$p\!\!\not|\ c$时无解。

由于$k,p$不一定互质,我们不能直接通过逆元来转化。

不过,我们仍然能尝试求解$kx+py=c$,无解则原方程组无解。

否则由斐蜀定理得$\gcd(k,p)|c$,设$d=\gcd(k,p)$。

则有$\dfrac{k}{d}x+\dfrac{p}{d}y=\dfrac{c}{d}$.

我们对$\dfrac{p}{d}$取模即得到$\dfrac{k}{d}x=\dfrac{c}{d}\pmod {\dfrac{p}{d}}$

由于$\dfrac{k}{d}\perp\dfrac{p}{d}$,我们就可以求逆元变为经典形式了。

剩下的就是一个扩展中国剩余定理。

#include<algorithm>
#include<cstdio>
#include<set>
#define Itor set<ll>::iterator
#define ll long long
#define MaxN 100500
using namespace std;
const int mod=998244353;
ll mul(ll a,ll b,ll m)
{return (((a>>20)*b%m<<20)+(a-(a>>20<<20))*b)%m;}
ll gcd(ll a,ll b)
{return !b ? a : gcd(b,a%b);}
ll lcm(ll a,ll b)
{return a/gcd(a,b)*b;}
void exgcd(ll a,ll b,ll &x,ll &y){
  if (!b){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=(a/b)*x;
}
ll inv(ll a,ll m){
  ll x,y;exgcd(a,m,x,y);
  return (x+m)%m;
}
bool fl;
void merge(ll &c1,ll &p1,ll c2,ll p2)
{
  ll c=(c2-c1%p2+p2)%p2,d=gcd(p1,p2);
  if (c%d){puts("-1");fl=1;return ;}
  ll k,y;exgcd(p1,p2,k,y);
  ll p=lcm(p1,p2);
  c1=(c1+mul(mul(k,p1,p),c/d,p))%p;
  p1=p;
}
multiset<ll> s;
ll a[MaxN],k[MaxN],p[MaxN],t[MaxN]
  ,mx,tc,tp;
void calc(ll k,ll c,ll p)
{
  mx=max(mx,(c-1)/k+1);
  if (k%p==0){
    if (c%p==0)return ;
    else {puts("-1");fl=1;return ;}
  }
  ll d=gcd(k,p);
  if (c%d){puts("-1");fl=1;return ;}
  k/=d;p/=d;c/=d;
  c=mul(c,inv(k,p),p);
  merge(tc,tp,c,p);
}
int n,m;
void solve()
{
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
  for (int i=1;i<=n;i++)scanf("%lld",&p[i]);
  for (int i=1;i<=n;i++)scanf("%lld",&t[i]);
  s.clear();
  for (int i=1;i<=m;i++){
    ll x;scanf("%lld",&x);
    s.insert(x);
  }
  for (int i=1;i<=n;i++){
    Itor it=s.upper_bound(a[i]);
    if (it!=s.begin())it--;
    k[i]=*it;s.erase(it);
    s.insert(t[i]);
  }
  mx=0;tp=1;tc=0;fl=0;
  for (int i=1;i<=n&&!fl;i++)
    calc(k[i],a[i],p[i]);
  if (fl)return ;
  ll tk=mx/tp;
  while(tk*tp+tc<mx)tk++;
  printf("%lld\n",tk*tp+tc);
}
int main()
{
  int T;scanf("%d",&T);
  while(T--)solve();
  return 0;
}

• P4720 【模板】扩展卢卡斯

跟普通卢卡斯定理关系不大 (

我们把模数分解成$\prod p_i^{c_i}$的形式,对于每个$p^c$单独求解,然后使用普通中国剩余定理合并即可。

考虑$\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}\pmod{p^c}$

但这毫无作用,往往有 $p|(n!)$ ,这样就无法求逆了。

考虑将$p$的幂次提尽,设$v(n)$为$n$中含有$p$的幂次。

则有$\dfrac{n!}{p^{v(n)}}≠0\pmod{p^c}$,这样就可以求逆了。设$r(n)=\dfrac{n!}{p^{v(n)}}$

我们计算$\dfrac{r(n)}{r(m)r(n-m)}p^{v(n)-v(m)-v(n-m)}$即可得到$\dbinom{n}{m}$。

上文介绍了$v(n)=\sum\limits_{i=0}\lfloor n/p^i\rfloor$ ,现在问题变为求$r(n)$.

对于$n!=1*2*3*...*n$,我们可以把其中为$p$的倍数的项提出来。

变为$\Big[1*2*...*(p-1)\Big]*p*\Big[(p+1)(p+2)...(p+p-1)\Big]*2p*...$

对于中间的每一块,$\prod_{i=1}^{p-1}(kp+i)\pmod {p^c}$,可以变为$[0,p^c)$中的某一段连乘积,维护阶乘及其逆元即可。

这样的段会有$O(n/p)$个,但是由于$\bmod\ p^c$,我们可以批量计算。

具体见代码,注意散块的边界情况。这样计算一次的复杂度是$O(p^c)$的。

对于那些为$p$的倍数的位置,共$\lfloor n/p\rfloor$个,统一除以$p$之后,又变成了$1*2*3*...$

于是就变为求解$r(\lfloor n/p\rfloor)$.

预处理复杂度为$O(\sum p_i^{c_i})$,回答一次的复杂度为$O(\log^2 p)$.

( 如果采用欧拉定理+光速幂可以达到$O(\sqrt{p}+\sum p_i^{c_i})$预处理$O(\log p)$回答 )

#include<algorithm>
#include<cstdio>
#define MaxN 1005000
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &x,ll &y){
  if (b==0){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=(a/b)*x;
}
ll inv(ll a,ll m){
  ll x,y;exgcd(a,m,x,y);
  return (x%m+m)%m;
}
ll powM(ll a,ll t,int mod)
{
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
ll v(ll n,int p){
  ll ret=0;
  while(n)ret+=(n/=p);
  return ret;
}
ll sav[MaxN];
ll r(ll n,int p,int mod){
  if (n==0)return 1;
  return powM(sav[mod-1],n/mod,mod)*sav[n%mod]%mod*r(n/p,p,mod)%mod;
}
ll C(ll n,ll m,int p,int mod)
{
  int c=v(n,p)-v(m,p)-v(n-m,p);
  ll ans=powM(p,c,mod);
  if (!ans)return 0;
  sav[0]=1;
  for (int i=1;i<mod;i++)
    if (i%p==0)sav[i]=sav[i-1];
    else sav[i]=sav[i-1]*i%mod;
  ans=ans*r(n,p,mod)%mod;
  ans=ans*inv(r(m,p,mod),mod)%mod;
  ans=ans*inv(r(n-m,p,mod),mod)%mod;
  return ans;
}
ll ret,mp=1;
void add(ll c,ll p)
{
  ll sp=mp*p;
  ret=(ret*inv(p,mp)%sp*p+mp*inv(mp,p)%sp*c)%sp;
  mp=sp;
}
ll n,m;int p;
int main()
{
  scanf("%lld%lld%lld",&n,&m,&p);
  int d=2;
  while(d*d<=p){
    if (p%d==0){
      int mod=1;
      while(p%d==0){
        p/=d;
        mod*=d;
      }add(C(n,m,d,mod),mod);
    }d++;
  }if (p>1)add(C(n,m,p,p),p);
  printf("%lld",ret);
  return 0;
}

• 例题① : P2183 [国家集训队]礼物

  题意 : 有$n$个不同的小球,投入$m$个盒子里面,钦定第$i$个盒子要投$w_i$个球,问方案数。

  对 $mod$ 取模,保证 $mod\leq 10^9$ 且分解之后的每个 $p^c\leq 10^5$

  $m\leq 5,n\leq 10^9$ ,时限$\texttt{1s}$.

先判掉无解的情况。设$S[k]=\sum\limits_{i=1}^kw_i$

不难发现题目叫我们求的是$\prod\limits_{i=1}^m\dbinom{n-S[i-1]}{w_i}$

也就是在固定模数下求解$m$次组合数,套用EXLucas即可。

理论复杂度为$O(\sqrt{p}+\sum p^c+m\log^2p)$,但是$O\Big(m(\sqrt{p}+\sum p^c+\log^2p)\Big)$也能过我就偷懒了。

评测记录

• 例题② : P3726 [AH2017/HNOI2017]抛硬币

  题解Link