组合数学专题！
最近 noip 考完了，决定试试冲冲省选，虽然没什么希望。
无望的努力也是一种独特的体验吧。
之后如果可能，会写一个 OI 经历的博客，最近真的有点迷茫，先学再说。
1. 推式子
例 1.1
题意
一个有 \(N\) 个元素的集合有 \(2^N\) 个不同子集（包含空集），现在要在这 \(2^N\) 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 \(K\)，求取法的方案数，答案模 \(1000000007\)。
题解
我的离谱思路里程
先选交集的 \(k\) 个元素，\(\displaystyle{\binom{n}{k}}\) 种方案。
剩下的元素有 \(n-k\) 个，包含选出的 \(k\) 个元素的集合数一共是 \(2^{n-k}\)
然后你需要选若干个集合，方案数 \(2^{2^{n-k}}\)，因为要至少一个，所以 \(2^{2^{n-k}}-1\)
嗯嗯然后会多考虑交集元素个数大于 \(k\) 的情况
于是答案就是 \(\displaystyle{\binom{n}{k}(2^{2^{n-k}}-1)-\binom{n}{k+1}(2^{2^{n-k-1}}-1)}\)
代入发现是错的
为什么呢？因为 \(\displaystyle{\binom{n}{k}(2^{2^{n-k}}-1)}\) 中元素个数 \(k+1\) 的会被算 \(\displaystyle{\binom{k+1}{k}}\) 次，后面只减了一次，肯定是错的。
那我们这样不就完了吗？ \(\displaystyle{\binom{n}{k}(2^{2^{n-k}}-1)-\binom{k+1}{k}\binom{n}{k+1}(2^{2^{n-k-1}}-1)}\)
还是错的 为什么呢？因为元素个数 \(k+2\) 的也会被多减！我们到这就看出来是 容斥 了。
用人类智慧猜一猜 \(\displaystyle{\sum_{k\le i\le n}(-1)^{i-k}\binom{i}{k}\binom{n}{i}(2^{2^{n-i}}-1)}\)
交上去是对的。交完我证了一下容斥，发现是对的（容斥只要证明后面的答案计算次数是 \(0\) ）
（事实上，把 \(-1\) 去掉，式子改成 \(\displaystyle{\sum_{k\le i\le n}(-1)^{i-k}\binom{i}{k}\binom{n}{i}2^{2^{n-i}}}\) 也是对的）
正确的思路历程
设 \(F_i\) 表示 \(i\) 个元素的集合，选择若干个子集，他们的交集为空集的方案数，那我们的答案就是 \(\displaystyle{\binom{n}{k}F_{n-k}}\)
然后呢，我们发现 \(\displaystyle{\sum_{i=0}^n \binom{n}{i}F_{n-i}}\) 就是全部的方案数，即 \(2^{2^n}\)
于是 \(\displaystyle{\sum_{i=0}^n \binom{n}{i}F_{i}}=2^{2^n}\)
二项式反演即得上述式子
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9+7, N = 1e6+5;
int n,k;
int ksm(int a, int b, int p)
{
int res=1;
for(; b; b>>=1,a=(ll)a*a%p) if(b&1) res=(ll)a*res%p;
return res;
}
int fc[N],fci[N];
int C(int n, int m)
{
if(m<0 or n<0 or n<m) return 0;
return (ll)fc[n]*fci[m]%P*fci[n-m]%P;
}
int main()
{
scanf("%d%d",&n,&k);
fc[0]=1;
for(int i=1; i<=n; i++) fc[i]=(ll)fc[i-1]*i%P;
fci[n]=ksm(fc[n],P-2,P);
for(int i=n; i; i--) fci[i-1]=(ll)fci[i]*i%P;
int sgn=1; ll ans=0;
for(int i=k; i<=n; i++)
{
int res=(ll)C(n,i)*C(i,k)%P*(ksm(2,ksm(2,n-i,P-1),P)%P-1+P)%P;
ans=(ans+res*sgn+P)%P; sgn=-sgn;
}
printf("%lld\n",ans);
return 0;
}
二项式反演
\[g_n=\sum^n_{i=0}\binom{n}{i}f_i⇒f_n=\sum^n_{i=0}(−1)^{n−i}\binom{n}{i}g_i \]我一直以为这东西很难，需要高端的组合技巧。
事实上它的难点是背式子！这东西其实非常好证（
首先你得会这两个式子
一些前置的组合数性质
1
\[\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \]左边：从 \(n\) 个数选 \(m\) 个，再从 \(m\) 个数选出 \(k\) 个
右边：从 \(n\) 个数选 \(k\) 个，再从剩下的 \(n-k\) 里选 \(m-k\) 个
这两个显然是等价的！（事实上大部分组合数性质都有组合解释）
2 二项式定理的推论
二项式定理
\[\sum_{i=0}^{n}\binom{n}{i}a^ib^{n-i}=(a+b)^n \]证明自己搜，这是数学基础知识）
由这个我们有一些推论
\[\sum_{i=0}^{n}\binom{n}{i}(-1)^i=(-1+1)^n=[n=0]\\ \sum_{i=0}^{n}\binom{n}{i}=(1+1)^n=2^n \]二项式反演的证明
你要证这个：
\[g_n=\sum^n_{i=0}\binom{n}{i}f_i⇒f_n=\sum^n_{i=0}(−1)^{n−i}\binom{n}{i}g_i \]带进去不就好了：
\[\Leftarrow f_n=\sum^n_{i=0}(−1)^{n−i}\binom{n}{i}\sum^i_{j=0}\binom{i}{j}f_j \]交换求和号：
\[\Leftarrow f_n=\sum^n_{j=0}f_j\sum^n_{i=j}(−1)^{n−i}\binom{n}{i}\binom{i}{j} \]注意到右边的式子可以化（运用上述的两个性质）：
\[\begin{align*} &\sum^n_{i=j}(−1)^{n−i}\binom{n}{i}\binom{i}{j}\\ =&\sum^n_{i=j}(−1)^{n−i}\binom{n}{j}\binom{n-j}{i-j}\\ =&\binom{n}{j}\sum^n_{i=j}(−1)^{n−i}\binom{n-j}{i-j}\\ =&\binom{n}{j}\sum^{n-j}_{i=0}(−1)^{n−i+j}\binom{n-j}{i}\\ =&\binom{n}{j}(−1)^{n+j}\sum^{n-j}_{i=0}(−1)^{i}\binom{n-j}{i}\\ =&\binom{n}{j}(−1)^{n+j}[n-j=0]\\ =&[n=j] \end{align*} \]于是我们就要证：
\[\Leftarrow f_n=\sum^n_{j=0}f_j[n=j] \]这显然 诶这不就证完了！
2 网格图路径计数
做了好多这种题，我们做个总结！反正类似卡塔兰数
多次容斥的套路题
就是两条线之间夹着，反复对称
例2.1.1
把求最长不下降子序列数转成网格图路径计数
例2.1.2
例2.1.3
例 2.2 （未限制方向的方案数）
多重集排列
\(\displaystyle\frac{n!}{m_1!m_2!\dots m_k!}\)
范德蒙德卷积
\(\displaystyle{\sum_i{\binom{n}{i}\binom{m}{k-i}}=\binom{n+m}{k}}\)
组合意义：从 \(n+m\) 选 \(k\) 个，可以枚举在 \(n\) 个中选择 \(i\) 个，则 \(m\) 个中就选择 \(k-i\) 个
常见套路——坐标系转化
\((x,y)\rightarrow (x+y,x-y)\)
\((0,\pm1)\rightarrow(\pm1,\mp1)\)
\((\pm1,0)\rightarrow(\pm1,\pm1)\)
例2.3
\((0,0)\) 到 \((n,m)\) 的方案数，不能经过障碍点
题解
设 \(f_i\) 表示第一次到达的是 \(i\) 号障碍点。
转移显然
代码
#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const ll N = 2e5+5;
const ll M = 3e3+5;
const ll mod = 1e9+7;
typedef pair<ll,ll> P;
ll n,m,k,mn;
ll fc[N],fci[N];
ll f[N];
P h[N];
ll qpw(ll a, ll b)
{
ll ans=1;
for(;b;b>>=1)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
}
return ans;
}
void prework()
{
fc[0]=1;
for(ll i=1; i<=mn; i++)
fc[i]=fc[i-1]*i%mod;
fci[mn]=qpw(fc[mn],mod-2);
for(ll i=mn-1; i>=0; i--)
fci[i]=fci[i+1]*(i+1)%mod;
}
inline ll C(ll yy, ll xx) {return fc[yy]*fci[xx]%mod*fci[yy-xx]%mod; }
int main()
{
scanf("%lld%lld%lld",&n,&m,&k); mn=n+m;
for(ll i=1; i<=k; i++) scanf("%lld%lld",&h[i].x,&h[i].y);
sort(h+1,h+1+k);
h[++k]=make_pair(n,m);
prework();
for(ll i=1; i<=k; i++)
{
f[i]=C(h[i].x+h[i].y,h[i].x);
for(ll j=1; j<i; j++)
f[i]=(f[i]-f[j]*C(h[i].x+h[i].y-h[j].x-h[j].y,h[i].x-h[j].x)%mod+mod)%mod;
}
printf("%lld\n",f[k]);
return 0;
}