首页 > 其他分享 >二项式反演

二项式反演

时间:2024-05-30 20:21:37浏览次数:21  
标签:aligned frac cdot sum 反演 binom 二项式

二项式反演

简介

二项式反演可以用来解决一些计数问题,是连接 至少/至多恰好 两类函数的桥梁。

形式一

\[f(n) = \sum_{i=0}^n (-1)^i \binom{n}{i} g(i) \\ g(n) = \sum_{i=0}^n (-1)^i \binom{n}{i} f(i) \]

证明

代 \(g(n)\) 入第一条式子。

\[\begin{aligned} f(n) &= \sum_{i=0}^n (-1)^i \binom{n}{i} g(i) \\ &= \sum_{i=0}^n (-1)^i \binom{n}{i} \sum_{j=0}^i (-1)^j \binom{i}{j} f(j) \end{aligned} \]

考虑每一个 \(f(j)\) 的系数。

\[\begin{aligned} f(n) &= \sum_{i=0}^n \sum_{j=i}^n (-1)^j \binom{n}{j} (-1)^i \binom{j}{i} \cdot f(i) \\ &= \sum_{i=0}^n \sum_{j=i}^n (-1)^{j-i} \binom{n}{i} \binom{n-i}{j-i} \cdot f(i) \\ &= \sum_{i=0}^n \binom{n}{i} \sum_{j=i}^n (-1)^{j-i} (1)^{n-j} \binom{n-i}{j-i} \cdot f(i) \\ &= \sum_{i=0}^n \binom{n}{i} \sum_{j=0}^{n-i} (-1)^{j} (1)^{n-i-j} \binom{n-i}{j} \cdot f(i) \\ &= \sum_{i=0}^n \binom{n}{i} (1-1)^{n-i} f(i) \\ &= f(n) \end{aligned} \]

得证。

形式二

\[f(n) = \sum_{i=0}^n \binom{n}{i} g(i) \\ g(n) = \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} f(i) \]

证明

\[h(n) = (-1)^n g(n) \]

所以

\[g(n) = (-1)^n h(n) \]

代入

\[f(n) = \sum_{i=0}^n (-1)^i \binom{n}{i} h(i) \]

由形式一

\[h(n) = \sum_{i=0}^n (-1)^i \binom{n}{i} f(i) \]

代回

\[g(n) = \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} f(i) \]

形式三

\[f(n) = \sum_{i=m}^n \binom{n}{i} g(i) \\ g(n) = \sum_{i=m}^n (-1)^{n-i} \binom{n}{i} f(i) \]

不难发现同形式一、二相比只改变了下界,然而这并不影响任何性质。

形式四

\[f(n) = \sum_{i=n}^m \binom{i}{n} g(i) \\ g(n) = \sum_{i=n}^m (-1)^{i-n} \binom{i}{n} f(i) \]

证明

思路与形式一差不多。

重新证明一遍。

代入 \(g(n)\)。

\[\begin{aligned} f(n) &= \sum_{i=n}^m \binom{i}{n} g(i) \\ &= \sum_{i=n}^m \binom{i}{n} \sum_{j=i}^m (-1)^{j-i} \binom{j}{i} f(j) \\ &= \sum_{i=n}^m \sum_{j=n}^i \binom{j}{n} (-1)^{i-j} \binom{i}{j} \cdot f(i) \\ &= \sum_{i=n}^m \sum_{j=n}^i (-1)^{i-j} \binom{i}{n} \binom{i-n}{i-j} \cdot f(i) \\ &= \sum_{i=n}^m \binom{i}{n} \sum_{j=n}^i (-1)^{i-j} (1)^{j-n} \binom{i-n}{i-j} \cdot f(i) \\ &= \sum_{i=n}^m \binom{i}{n} (1-1)^{i-n} f(i) \\ &= f(n) \end{aligned} \]

应用

其中,形式三、四是经常用到的。

P1595 信封问题

错位排列问题。

设 \(f(i)\) 表示恰有 \(i\) 个信封在正确的位置上。

\(g(i)\) 表示至少 \(i\) 个信封在正确的位置上。

容易求得

\[g(i) = \binom{n}{i}(n-i)! \]

并有如下关系

\[g(i) = \sum_{j=i}^n \binom{j}{i} f(j) \]

利用形式四进行二项式反演。

\[f(i) = \sum_{j=i}^n (-1)^{j-i} \binom{j}{i} g(j) \]

所求答案即为

\[\begin{aligned} f(0) &= \sum_{j=0}^n (-1)^{j-0} \binom{j}{0} g(j) \\ &= \sum_{i=0}^n (-1)^i \binom{n}{i}(n-i)! \end{aligned} \]

P4491 [HAOI2018] 染色

首先 \(K\) 最大为 \(\min{(\frac{N}{S},M)}\)。

恰好 出现 \(i\) 次的方案数为 \(f(i)\)。

至少 出现 \(i\) 次的方案数为 \(g(i)\)。

可以计算 \(g(i)\)

  • 首先选定 \(i\) 种颜色 乘上 \(\binom{M}{i}\)
  • 选定 \(iS\) 个位置 乘上 \(\binom{N}{iS}\)
  • 考虑内部顺序 乘上 \((iS)!\)
  • 内部顺序中,相同颜色交换算一种 除以 \((S!)^i\)
  • 剩下位置随意 \(N-iS\) 个位置 \(M-i\) 种颜色 乘上 \((M-i)^{n-iS}\)

\[g(i) = \frac{\binom{M}{i} \binom{N}{iS} (iS)! (M-i)^{n-iS}}{(S!)^i} \]

又有关系

\[g(i) = \sum_{j=i}^K \binom{j}{i} f(j) \]

根据形式四,二项式反演

\[f(i) = \sum_{j=i}^K (-1)^{j-i} \binom{j}{i} g(j) \]

答案为:

\[\sum_{i=0}^K W[i] f(i) \]

故需要快速的求出所有的 \(f(i)\)。

我们可以在 \(O(n)\) 的时间复杂度内预处理出所有的 \(g\)。

如果暴力求 \(f(i)\) 时间复杂度来到 \(O(n^2)\)。

尝试卷积,拆开组合数

\[\begin{aligned} f(i) &= \sum_{j=i}^K (-1)^{j-i} \frac{j!}{i!(j-i)!} g(j) \\ &= \frac{1}{i!}\sum_{j=i}^K \frac{(-1)^{j-i}}{(j-i)!} \cdot j! g(j) \end{aligned} \]

我们进行了分离的操作,可以尝试卷积。

\[A(i) = \frac{(-1)^i}{i!} \\ B(i) = i! g(i) \]

故有

\[f(i) = \frac{1}{i!}\sum_{j=i}^K A(j-i) \cdot B(j) \]

翻转 \(B\) 得到 \(C\),即令 \(B(i) = C(K-i)\)。

翻转 \(f\) 得到 \(F\),即令 \(f(i) = F(K-i)\)。

故有

\[F(K-i) = \frac{1}{i!}\sum_{j=i}^K A(j-i) \cdot C(K-j) \]

已经看出卷积的形式了,使用 NTT 卷积即可。

参考代码

标签:aligned,frac,cdot,sum,反演,binom,二项式
From: https://www.cnblogs.com/DeepSeaSpray/p/18223153

相关文章

  • 莫比乌斯函数和莫比乌斯反演
    莫比乌斯函数定义莫比乌斯函数为\(\mu(n)=\begin{cases}1&n=1\\(-1)^r&&n=p_1\timesp_2\timesp_3\cdots\cdotsp_r\\0&\text{其他}\end{cases}\)。定理:\(\sum_{d|n}\mu(d)=\begin{cases}1&n=1\\0&n>......
  • 狄利克雷卷积与莫比乌斯反演
    狄利克雷卷积与莫比乌斯反演主要内容数论函数狄利克雷卷积积性函数莫比乌斯反演数论分块提要\(a\botb\)表示\(a\)与\(b\)互质。数论函数数论函数是一类定义域是正整数的函数,可以类比数列。加法,数乘比较简单,略过。狄利克雷卷积定义两个数论函数的狄利克雷卷......
  • 莫比乌斯反演即狄利克雷卷积速通
    莫比乌斯反演速通前言由于请假错过了讲课,所以莫反是我第一个需要自学的难度不小的数学知识。自学的过程的狼狈的,旁边也曾是自学的czn告诉我如果学会“狄利克雷卷积”就可以对“莫比乌斯反演”的理解进行“降维打击”。他还十分热心地带着我速通了一遍狄卷与莫反。一知半解,就......
  • CF1278F Cards(斯特林数+二项式定理)
    题意简述有\(m\)张牌,其中有一张是王牌。你现在可以洗\(n\)次牌(每种牌堆序列等概率出现),然后查看牌堆顶的第一张牌。设\(x\)为\(n\)次洗牌中第一张牌是王牌的次数,则得分为\(x^k\)。求得分的期望值对\(998244353\)取模的值。\(1\len,m<998244353,k\le5000\)分析将......
  • [数论] 二项式反演
    菜就多练,输不起就别玩,不会就是不会。二项式推论\(1.\)\(\tbinom{n}{m}=\tbinom{n}{n-m}\)\(2.\)\(\tbinom{n}{m}=\frac{n}{m}\tbinom{n-1}{m-1}\)\(3.\)\(\sum\limits_{i=0}^nC_n^i=2^n\)证明:拆\((1+1)^n\)\(4.\)\(\sum\limits_{i=0}^n(-1)^iC_n^i=0\)特殊的,......
  • 二项式反演
    算法核心二项式反演与莫比乌斯反演类似,都可以用于在给定的条件式实现两个函数之间的相互推算。二项式反演适用于,其核心反演式子有二:\[f(n)=\sum_{i=0}^n(-1)^iC_n^ig(i)\iffg(n)=\sum_{i=0}^n(-1)^iC_n^if(i)\]\[f(k)=\sum_{i=k}^nC_i^kg(i)\iffg(k)......
  • 单位根反演小记
    反演公式\[[n|v]=\frac{1}{n}\sum_{0\lej<n}(\omega_n^v)^j\]证明很简单,等比数列求和即可。应用牛客Wannafly挑战赛11E白兔的***难题意:给定\(k\le2^20,n\le10^{16},p=998244353\),求\(t\in[0,k)\),\(a_t=\sum_{k|i,0\lei+t\len}\binom{n}{i+......
  • 二项式系数
    二项式系数更完整的思考过程以及代数推理过程都可以看数学书,所以我尽量给每个式子都赋予组合意义。因为在有足够强的代数推理能力之前,没有组合意义往往是困难的。恒等式赋予组合意义往往都是左边右边分开找意义。常见公式:\[\begin{aligned}\binom{n}{k}&=\binom{n}{n-k}\en......
  • 小红不想做莫比乌斯反演杜教筛求因子和的前缀和(枚举)--牛客周赛 Round 39-E
    #include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'#defineinf1e18constintmod=1e9+7;constintN=2e5+5;intn,m,p,x;voidsolve(){ cin>>n>>m>>p>>x; intans=0; for(inti=1;i&......
  • 莫比乌斯反演
    莫比乌斯反演莫比乌斯函数\(\mu(d)\)是积性函数\[\sum_{d|n}\mu(d)=[n=1]\]反演的两种形态设F,f为数论函数\[F(n)=\sum_{d|n}f(d)\]用狄利克雷卷积的简要证明\[F=f*I\\\becauseI*\mu=\epsilon\\F*\mu=f*I*\mu\\F*\mu=f\]四大要点公式推导:等价变换:线性筛法:分块处......