组合数学
一些公式
- 组合数定义: (C_n^m=frac{n!}{m!(n-m)!}) .意义是从 (n) 个元素中选出 (m) 个元素的方案数,可记作(n choose m).
- 常用性质: (C_n^m=C_n^{n-m},C_n^0=1,C_n^1=n,C_n^n=1,C_n^m=0 when m>n).
- 递推公式:(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}).不选最后一个元素的方案数加选最后一个元素的方案数.
- 求和:(sum_{i=0}^n {m+ichoose i}={m+n+1choose n}).(sum_{i=0}^n {ichoose m}={n+1choose m+1}).
- 二项式定理:((a+b)^n=sum_{i=0}^n {nchoose i}*a^i*b^{n-i}).
- 牛顿广义二项式定理:((a+b)^alpha=sum_{i=0}^{infty} {alphachoose i}a^k b^{alpha-k},alpha in mathbb{R}).({alphachoose i}=frac{(alpha)(alpha-1)...(alpha-k-1)}{i!}).这个在做生成函数的时候会用到.
- (Lucas) 定理:({nchoose m} equiv {n\%p choose m\%p}*{lfloor n/p floor choose lfloor m/p floor} (mod p),pin P).
常用求组合数方法
- 由于组合数涉及到阶乘, (n,m) 稍大一些结果就会很大,一般在模意义下求,下面只在模 (p) 意义下进行讨论.
- 设要求的是({n_0choose m_0},n_0leq n).有时候只需要求一个或少个,有时候需要求很多个.
定义法
- 求一个:([m_0+1,n_0])的积做分子,([1,n_0-m_0])的积做分母,边乘边除.
- 分子分母都只有 (n-m) 个. (m) 可与 (n-m) 取较大值.
- 时间复杂度:每次求(O(m)).
- 求多个:预处理出 ([0,n]) 内的阶乘及阶乘逆元,阶乘逆元先求 (n!) 的逆元,再一个个乘回来得到其他的.需要计算时直接用定义计算即可.
- 时间复杂度:预处理(O(n+logp)),每次求(O(1)).
杨辉三角/递推法
- 求多个:利用公式 ({nchoose m}={n-1choose m}+{n-1choose m-1}) 递推计算.初始化为({0choose 0}=1,{nchoose 1}=n).
- 时间复杂度:递推预处理(O(n^2)),每次求(O(1)).
- 直接使用此法空间为 (O(n^2)) ,可滚动数组优化,但无法查询多个.
- 不容易中途溢出.
(Lucas)定理法
- 求多个:若(pin P),预处理 (p) 以内的阶乘和阶乘逆元,根据(Lucas)定理递归,当 (n_0<p) 时使用定义直接计算.
- 时间复杂度:预处理(O(p)),每次求(O(logp)).
- 适用于 (pin P)且较小,(n,m)较大的情况.
- 若 (p otin P),但 (p) 的每个质因数次数不超过 (1) ,可将 (p) 质因数分解,(p=prod p_i),对每个(p_i)分别用(Lucas)定理计算,最后使用 (crt) 合并答案. 适用于(n,m)较大,且 (p) 在题面中已知,分解后每个质因数次数为(1),且都较小的情况.
- 条件比较苛刻,但确实某些题(古代猪文)会用到.
题目
古代猪文
- 题意:给出(G,n),求(G^{sum_{k|n} {nchoose k}} mod 999911659,G,nleq 1e9).
- 题目中所给模数为质数,考虑使用费马小定理,则只需计算出(sum_{k|n} {nchoose k} mod 999911658),然后使用快速幂即可.
- 考虑(O(sqrt n))暴力枚举约数 (k) ,每次计算 ({nchoose k}) ,但模数, (n,k) 都是 (10^9) 数量级的,算一个也无法接受.
- 注意到 (999911658) 是个合数,将其质因数分解,我们惊奇发现:(999911658=2*3*4679*35617),最大的质因子只有 (10^4) 级.
- 考虑使用 (Lucas) 定理,计算出 ({nchoose k}) 对这 (4) 个质因子分别取模得到的结果,最后使用 (crt) 合并答案即可.
- 时间复杂度为(O(p_{max}+sqrt n * log p_{max}),p_{max}=35617).
- 在洛谷水双倍经验的时候发现了一个问题,当 (G) 与 (P=999911659) 不互质时,指数对 (varphi (P)) 取模的推论不能使用,需特判.这里 (P) 为质数,不互质的情况答案显然为 (0) .
- 涉及知识点较多.
#include"bits/stdc++.h"
#define int long long
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;###
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int P=999911659;
int prime[4]={2,3,4679,35617};
int mul(int a,int b,int mod)
{
return 1LL* a * b % mod;
}
int add(int a,int b,int mod)
{
return (a + b) % mod;
}
int fpow(int a,int b,int mod)
{
int res=1;
while(b)
{
if(b&1)
res=mul(res,a,mod);
a=mul(a,a,mod);
b>>=1;
}
return res;
}
int inv(int x,int mod)
{
return fpow(x,mod-2,mod);
}
int N,G;
int a[4];
int fac[4][36000];
void pre(int x)
{
fac[x][1]=fac[x][0]=1;
for(int i=2;i<prime[x];++i)
fac[x][i]=mul(fac[x][i-1],i,prime[x]);
}
int C(int n,int m,int x)//n choose m
{
if(n<m)
return 0;
int res=fac[x][n];
res=mul(res,inv(fac[x][m],prime[x]),prime[x]);
res=mul(res,inv(fac[x][n-m],prime[x]),prime[x]);
return res;
}
int Lucas(int n,int m,int x)
{
if(!m)
return 1;
return mul(C(n%prime[x],m%prime[x],x),Lucas(n/prime[x],m/prime[x],x),prime[x]);
}
void solve(int k)
{
for(int x=0;x<4;++x)
a[x]=add(a[x],Lucas(N,k,x),prime[x]);
}
void exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;
y=0;
return;
}
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-(a/b)*y;
}
int crt()
{
int res=0;
int x,y;
for(int i=0;i<4;++i)
{
int tmp=(P-1)/prime[i];
exgcd(prime[i],tmp,x,y);
res=(res+y*a[i]%(P-1)*tmp)%(P-1);
}
return (res+P-1)%(P-1);
}
signed main()
{
N=read(),G=read();
if(G%P==0)
return puts("0")&1;
for(int i=0;i<4;++i)
pre(i);
for(int i=1;i*i<=N;++i)
{
if(N%i==0)
{
solve(i);
if(i*i!=N)
solve(N/i);
}
}
int tp=crt();
int ans=fpow(G,tp,P);
cout<<ans;
return 0;
}
牡牛和牝牛
- 题意:求长度为 (n) 且任意两个 (1) 之间至少有 (k) 个 (0) 的 (01) 串数目,(n,kleq 1e5),答案取模.
- (dp) 做法:令 (f[i]) 表示最后一个 (1) 在位置 (i) 上的方案数.有(forall i leq k+1,f[i]=1).(前面只能都是 (0) ).(forall i>k+1,f[i]=1+sum_{j=1}^{i-k-1} f[j])(前面都是 (0) 或枚举上个 (1) 的位置).
- 维护 (f) 的前缀和即可做到 (O(n)).加上全为 (0) 的情况,答案为(1+sum f[i]).
- 排列做法:枚举这个串中共有 (i) 个 (1),那么有 (max(0,(i-1)k)) 个 (0) 的位置是确定的.
- 只用考虑 (i) 个 (1) 和 (n-i-max(0,(i-1)k)) 个 (0) 的位置,是一个有重复元素的排列数目.
- 记每种元素有 (t_i) 个,易知排列数目为(frac{(sum t_i)!}{prod (t_i!)}).
#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int P=5000011;
inline int add(int a,int b)
{
return (a + b) % P;
}
inline int mul(int a,int b)
{
return 1LL * a * b % P;
}
const int MAXN=1e5+10;
int k,n;
int f[MAXN],sum[MAXN];
void solve_dp()
{
for(int i=1;i<=k+1;++i)
f[i]=1,sum[i]=add(sum[i-1],f[i]);
for(int i=k+2;i<=n;++i)
f[i]=add(sum[i-k-1],1),sum[i]=add(sum[i-1],f[i]);
printf("%d
",add(sum[n],1));
}
int fpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
int inv(int x)
{
return fpow(x,P-2);
}
int fac[MAXN];
void solve_math()
{
fac[0]=1;
for(int i=1;i<=n;++i)
fac[i]=mul(fac[i-1],i);
int ans=0;
for(int i=0;i<=n;++i)
{
int j=n-i-max(0,(i-1)*k);
if(j<0)
continue;
int up=fac[i+j];
int down=mul(fac[i],fac[j]);
ans=add(ans,mul(up,inv(down)));
}
printf("%d
",ans);
}
int main()
{
n=read(),k=read();
solve_math();
// solve_dp();
return 0;
}
方程的解
- 题意:给定 (k,x) ,求不定方程(a_1+a_2+a_3...+a_k=(x^x mod 1000)) 的正整数解组数.(kleq 100,xleq 2^{31}-1).
- 先使用快速幂求出方程右侧的值,记为 (n) .组数用隔板法解决,有 (n) 个小球,中间有 (n-1) 个空位,向这些空位中插入 (k-1) 个隔板,得到的 (k) 段小球数就是一组解.总组数为(n-1choose k-1).
- (PS):若要求非负整数解,加入(k) 个小球,最后从每段中减去一个即得.组数为(n+k-1choose k-1).
- 最后答案要用高精度.懒得写了.代码中的是对 (1e9+7) 取模.
#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int P=1000,p=1e9+7;
inline int mul(int a,int b,int mod)
{
return 1LL * a * b % mod;
}
int fpow(int a,int b,int mod)
{
int res=1;
while(b)
{
if(b&1)
res=mul(res,a,mod);
a=mul(a,a,mod);
b>>=1;
}
return res;
}
int inv(int x)
{
return fpow(x,p-2,p);
}
int C(int n,int m)//n choose m
{
if(n<m)
return 0;
int up=1,down=1;
if(m>n-m)
m=n-m;
for(int i=0;i<m;++i)
{
up=mul(up,n-i,p);
down=mul(down,m-i,p);
}
return mul(up,inv(down),p);
}
int main()
{
int k=read(),x=read();
int ans=C(fpow(x,x,P)-1,k-1);
printf("%d
",ans);
return 0;
}
序列统计
- 题意:给定 (n,l,rleq 1e9) ,问长度不超过 (n) ,元素为整数且在 ([l,r]) 内的不下降序列的数目,答案对 (1e6+3) 取模.(100) 组数据.
- 容易发现,答案与区间长度 (L=r-l+1) 有关.不妨考虑所有元素在 ([1,L]) 内,考虑将所有长度的不下降子序列数目加起来.
- 要得到一个长度为 (i) 的上升序列,我们可以把第 (k) 个数权值 (+k) ,变为求上升序列的问题,元素在 ([2,L+i]) 内,共 (L+i-1) 个数.
- 随意取出 (i) 个数正确排列即可,方案数为(L+i-1choose i).
- 所有的加起来,据求和公式得到答案(sum_{i=1}^{n} {L+i-1choose i}={n+Lchoose L}-{L+0-1choose 0}).
- 模数较小,使用 (Lucas) 定理计算即可.
#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int P=1e6+3;
inline int add(int a,int b)
{
return (a + b) % P;
}
inline int mul(int a,int b)
{
return 1LL * a * b % P;
}
int fpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
int inv(int x)
{
return fpow(x,P-2);
}
int fac[P+10],invfac[P+10];
void pre()
{
fac[0]=1;
for(int i=1;i<=P;++i)
fac[i]=mul(fac[i-1],i);
invfac[P-1]=inv(fac[P-1]);
for(int i=P-2;i>=0;--i)
invfac[i]=mul(invfac[i+1],i+1);
}
int C(int n,int m)
{
if(n<m)
return 0;//加上,利用lucas计算容易出现这种情况
int res=fac[n];
res=mul(res,invfac[m]);
res=mul(res,invfac[n-m]);
return res;
}
int Lucas(int n,int m)
{
if(!m)
return 1;
return mul(C(n%P,m%P),Lucas(n/P,m/P));
}
int L,n;
int main()
{
pre();
int T=read();
while(T--)
{
n=read();
int l=read(),r=read();
L=r-l+1;
int ans=(Lucas(n+L,n)-1+P)%P;
printf("%d
",ans);
}
return 0;
}
超能粒子炮・改
- 题意:给出 (n,kleq 1e18) ,求(sum_{i=0}^k {nchoose i} mod p, p=2333.)共 (1e5) 组数据.
- 下面的式子运算都在模意义下进行.
- 记(S(n,k)=sum_{i=0}^k {nchoose i}).利用 (Lucas) 定理将其展开,有
[egin{align*}
S(n,k)&=sum_{i=0}^k {nchoose i}\
&=sum_{i=0}^k {n/p choose i/p}*{n\%p choose i\%p}\
&=sum_{i=0}^{(k/p)-1} ({n/pchoose i}*sum_{j=0}^{p-1} {n\%p choose j})+sum_{i=(k/p)*p}^{k} {n/pchoose i/p}*{n\%p choose i\%p}\
&=sum_{i=0}^{(k/p)-1} {n/pchoose i}*sum_{j=0}^{p-1} {n\%p choose j}+sum_{i=0}^{k\%p}{n\%p choose i}*{n/p choose k/p}\
&=S(n/p,(k/p)-1)*S(n\%p,p-1)+S(n\%p,k\%p)*{n/p choose k/p}.
end{align*}
]
- (O(p^2)) 预处理出规模在 (p) 内的 (S) 和组合数.利用上式子及 (Lucas) 定理递归计算,显然单次为(O(log _pn)).总时间复杂度为(O(p^2+Tcdot log_pn))
#include"bits/stdc++.h"
#define int long long
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int P=2333;
inline int add(int a,int b)
{
return (a + b) % P;
}
inline int mul(int a,int b)
{
return a * b % P;
}
int s[P+10][P+10],c[P+10][P+10];
void init()
{
for(int i=0;i<=P;++i)
s[i][0]=c[i][0]=1;
for(int i=1;i<=P;++i)
s[0][i]=1;//注意需加上
for(int i=1;i<=P;++i)
{
for(int j=1;j<=i;++j)
c[i][j]=add(c[i-1][j],c[i-1][j-1]),s[i][j]=add(s[i][j-1],c[i][j]);
for(int j=i+1;j<=P;++j)
s[i][j]=s[i][j-1];//注意需加上
}
}
int C(int n,int m)// n choose m
{
if(n<m)
return 0;
if(!m)
return 1;
return mul(c[n%P][m%P],C(n/P,m/P));
}
int S(int n,int k)
{
if(n<P)
return s[n][k];
int res=mul(S(n/P,k/P-1),S(n%P,P-1));
res=add(res,mul(S(n%P,k%P),C(n/P,k/P)));
return res;
}
signed main()
{
init();
int T=read();
while(T--)
{
int n=read(),k=read();
printf("%lld
",S(n,k));
}
return 0;
}