排列组合脑子寄存处

球与盒子

• 下面记 $abc$ 表示 $球是否相同~(a)$ ，$盒子是否相同~(b)$，$盒子可否为空~(c)$。

• 球有 $n$ 个，盒子有 $m$ 个。

  球同	盒子相同	盒子不同
  不能为空	自然数拆分	$C_{n-1}^{m-1}$
  可以为空	自然数拆分	$C_{n+m-1}^{m-1}$

  球不同	盒子相同	盒子不同
  不能为空	$S2_{n,m}$	$m! \times S2_{n,m}$
  可以为空	$\sum^{n}\limits_{i=1} S2_{n,i}$	$m^n$

注：

$S2$ 表示第二类斯特林数。

通项公式为

$S2_{n,m}\;=\;\frac{1}{m!}\;\bigg( \sum\limits_{i=0}^m\,(-1)^k\times C_m^k\times(m-k)^n\; \bigg)$

int sign(int x) { return (x&1) ? -1 : 1; }
int C(int n,int m) { return fac[n]*inv[n-m]%M*inv[m]%M; }
int second_Stirling(int n,int m)
{
   int res=0; rep(i,0,m) res=(res+ sign(i)*C(m,i)*qmi(m-i,n,M)%M +M ) %M;
   return inv[m] * res %M;
}

---

排列组合恒等式

• 基础：二项式定理

$$ \begin{align} \sum\limits_{i=0}^n (-1)^i \times C_n^i &=0 \\ \sum\limits_{i=0}^n i \times C_n^i &= n\times 2^{n-1} \\ \sum\limits_{i=m}^n C_i^m &= C_{n+1}^{m+1} \\ \sum\limits_{i=0}^m C_n^iC_m^{r-i}&= C_{n+m}^{r} \\ C_n^r\times C_r^k &= C_n^k\times C_{n-k}^{r-k} \\ \sum\limits_{i=0}^n (C_i^n)^2 &= C_{n}^{2n} \\ \end{align} $$

---

扩展卢卡斯 (屎山) | exlucas

int cache_ret,cache_x,cache_y,cache_d,difference,fac[1000007];
int PrimeCount(int n,int p) { cache_ret=0;for(int i=p;i<=n;i*=p) cache_ret+=n/i;return cache_ret; }
int qmi(int a,int b,int mod) { int res=1; while(b) { if(b&1) res=res*a%mod; b>>=1; a=a*a%mod; } return res; }
void init(int p,int mod) { fac[2]=2; fac[1]=fac[0]=1;rep(i,2,mod) if(i%p==0) fac[i]=fac[i-1]; else fac[i]=fac[i-1]*i%mod; }
__int128 exgcd(int a,int b,__int128 &x,__int128 &y) { if(!b) { x=1,y=0; return a; } __int128 d=exgcd(b,a%b,y,x); y-=a/b*x; return d; }
void GetPrime(int x,vector<pair<int,int> > &ans) { rep(i,2,x) if(x%i==0) { ans.emplace_back((pair<int,int>){i,1}); while(x%i==0) ans.back().second*=i,x/=i; } }
int clac(int n,int p,int mod) {if(n==0) return 1; int cache_res=fac[mod-1];cache_res=qmi(cache_res,n/mod,mod);cache_res=(cache_res*fac[n%mod])%mod;cache_res=(cache_res*clac(n/p,p,mod))%mod;return cache_res;}
int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } cache_d=exgcd(b,a%b,y,x); y-=a/b*x; return cache_d; }int Inverse(int x,int p) { exgcd(x,p,cache_x,cache_y); while(cache_x<0) cache_x+=p; return cache_x; }
long long excrt(int len,int *r,int *m) { __int128 now=r[1],mod=m[1],tp,d,g,x,y; rep(i,2,len) { d=(__int128)exgcd((int)mod,m[i],x,y),g=m[i]/d; x*=(__int128)((__int128)r[i]-now)/d,x=(x%g+g)%g; tp=mod/(__int128)__gcd(mod,(__int128)m[i])*m[i]; now=((now+(__int128)mod*x)%tp+tp)%tp; mod=tp; } return (long long)now;}
int __exlucas(int n,int m,int p,int mod){if(m<0 || n<m) return 0;int numerator=clac(n,p,mod),denominator_first=clac(m,p,mod),denominator_second=clac(n-m,p,mod);if((difference=PrimeCount(n,p)-(PrimeCount(m,p)+PrimeCount(n-m,p)))>0) numerator=(numerator*qmi(p,difference,mod))%mod;return (numerator*Inverse(denominator_first,mod)%mod*Inverse(denominator_second,mod))%mod;}
int exlucas(int n,int m,int p) { vector<pair<int,int> > pos;static int idx,rr[64],mm[64]; idx=0; GetPrime(p,pos); for(auto i:pos) init(i.first,i.second),rr[++idx]=__exlucas(n,m,i.first,i.second),mm[idx]=i.second; return excrt(idx,rr,mm); }

---