Lucas定理模板题-acwing887
Lucas定理证明
类比acwing1308 方程的解–本题为不定方程
$$
L,R\\\\
=>\\\\
0 \sim R-L\\\\
=>\\\\
0 \leq a_{1} \leq … \leq a_{k} \leq R-L\\\\
=>\\\\
$$
$$
\begin{align}
令x_{1} &= a_{1}\\\\
x_{2} &= a_{2}-a_{1}\\\\
…&=…\\\\
x_{k} &= a_{k}-a_{k-1}\\\\
问题转化为\\\\
不等式解x_{1}+…+x_{k} &\leq R-L,x_{i} \geq 0\\\\
不等式解y_{1}+…+y_{k} &\leq R-L+k,y_{i}=x_{i}+1 > 0\\\\
则可以转化为隔板法问题\\\\
不等式右边视为R-L+k个小球,&一共有k个自变量-可以放k个隔板\\\\
(不等式-不用用完,所以是k {~}如果是等式&则要用完,所以是k-1,第k隔板后不算了)\\\\
&0|0…|....|…|…\\\\
&y_{1}{~}y_{2}{~}{~}{~}{~}{~}{~}{~}{~}{~}{~}{~}{~}y_{k}\\\\
则方案数&=C_{R-L+k}^{k}
\end{align}
$$
$$
\begin{align}
L \leq a_{1} \leq …& \leq a_{k} \leq R\\\\
b_{i}&=a_{i}+i-1=>\\\\
L \leq b_{1} <…& < b_{k} \leq R+k-1\\\\
转化为[L,R+k-1]中取k个数&=C_{R+k-1-L+1}^{k}\\\\
&=C_{R-L+k}^{k}\\\\
\end{align}
$$
答案
$$
\begin{align}
\sum_{k=1}^{N} C_{R-L+k}^{k}
&=C_{R-L+1}^{1}+C_{R-L+2}^{2}+…+C_{R-L+k}^{k}\\\\
&=C_{R-L+1}^{R-L}+C_{R-L+2}^{R-L}+…+C_{R-L+k}^{R-L}\\\\
(m=R-L)&=-C_{m+1}^{m+1}+C_{m+1}^{m+1}+C_{m+1}^{m}+…+C_{m+k}^{m}\\\\
(C_{a}^{b}=C_{a-1}^{b}+C_{a-1}^{b-1})&=-C_{m+1}^{m+1}+C_{m+2}^{m+1}+C_{m+2}^{m}+…+C_{m+k}^{m}\\\\
&=-C_{m+1}^{m+1}+C_{m+3}^{m+1}+C_{m+3}^{m}+…+C_{m+k}^{m}\\\\
…&=…\\\\
&=C_{m+k}^{m+1}+C_{m+k}^{m}-1\\\\
&=C_{m+k+1}^{m+1}-1\\\\
(m=R-L)&=C_{R-L+k+1}^{R-L+1}-1
\end{align}
$$
/*
数值:[4,5]
长度:[1,2]
长度==1:4,5
长度==2:44,45,55
枚举序列长度k 有多少单调不降序列在[L,R]
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int p=1000003;
int qmi(int a,int k)
{
int res = 1;////res初始化=1
while(k)
{
if(k&1) res = (LL)res*a%p;
a = (LL)a*a%p;
k>>=1;
}
return res;
}
//C_{a}^{b} = a!/(b!(a-b)!) = a*...*(a-b+1)/b!
int C(int a,int b)
{
if(a<b)return 0;
int down=1,up=1;
for(int i=a,j=1;j<=b;i--,j++)
{
up=(LL)up*i%p;
down = (LL)down*j%p;
}
// up/down % p = up*down(逆元)%p
return (LL)up*qmi(down,p-2)%p;
}
int Lucas(int a, int b)
{
if (a < p && b < p) return C(a, b);
return (LL)Lucas(a / p, b / p) * C(a % p, b % p) % p;
}
int main()
{
int T;
cin >> T;
while(T--)
{
int n, l, r;
cin >> n >> l >> r;
cout << (Lucas(r - l + n + 1, r - l + 1) - 1 + p) % p << endl;
}
return 0;
}
大佬,为啥这里的求组合数方法不是像基础课组合数3里那样边循环边求逆元,而是最后统一到最后再求逆元啊?
难道 $ inv(a/b) \equiv inv(a)*inv(b) $ ?
也可以呀,是 $inv(a\times b)\equiv inv(a)\times inv(b)$
老实人竟然也Latex了 呜呜呜