反演

莫比乌斯反演

积性函数

数论中的卷积默认是狄利克雷卷积,写作$*$,星号夹在两个函数中间.常见的积性函数有:

单位函数 $\varepsilon(n)=[n=1]$ ,完全积性
恒等函数 $\mathrm{id}_k(n)=n^k$ ,完全积性
常数函数 $1(n)=1$ ,完全积性
欧拉函数 $\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]$ 也就是小于等于n和n互质的数的个数
除数函数 $\sigma_k(n)=\sum_{d|n}d^k$ ,其中 $\sigma_0$ 经常记作 $d$ 或 $\tau$ ,$\sigma_1$经常记作$\sigma$ .
莫比乌斯函数 $\mu(n)=\begin{cases}1&n=1\\ 0&\exists d>1,d^2|n \\ (-1)^{\omega(n)}&otherwise\end{cases}$ ,是加性函数
(人话:1是1,有完全平方数就是0,否则就是按照积性函数-1之间相乘.)
$\omega(n)$ 表示n的本质不同质因子个数

(加性函数,指满足 $f(ab)=f(a)+f(b)$ 的函数)

积性函数推广:假如fg是积性函数,以下也都是积性函数:

$$f(x^p)\qquad f^p(x)\qquad f(x)g(x)\qquad f(x)*g(x)$$

狄利克雷卷积

对于两个数论函数fg,定义其结果h

$$h(x)=\sum_{d|x}f(d)g(\frac xd)=\sum_{ab=x}f(a)g(b)$$

即为

$$h=f*g$$

性质:交换律结合律分配律.有一个特殊点的:

$f=g$ 和 $f*h=g*h$ 是充要条件,其中 $h(1)\neq0$ .

高维前缀和:铺垫一下,优化有用.高位前缀和就是状压dp,用于快速求解集合及其子集和.

可以对这道题中的模型进行抽象化,即:对于任意数论函数f,积性函数g,在 $O(n\log\log n)$ 的时间复杂度内求出狄利克雷卷积h.

将每个质数视为一个维度,则狄利克雷卷积就是一个带系数的高维前缀和,考虑分别处理每一个维度 $p_i$ ,每个 $p_k$ 都是一个物品,每个物品只转移一次,所以是一个01背包(DP统计所有方案的价值总和).物品 $p_k$ 的体积为 $p_k$ (这里总体积是每个物品的体积相乘),价值为 $g(p_k)$ (价值也相乘).

常见卷积式子:

$$\mathrm{id}*\mu=\varphi$$ $$\varphi*1=\mathrm{id}$$ $$\mu*1=\varepsilon$$ $$1*1=\mathrm{d}$$ $$\mathrm d*\mu=1*\varepsilon=1$$

若

$$f(n)=\sum_{d|n}g(d)$$

则

$$g(n)=\sum_{d|n}\mu(d)f(\frac nd)$$ $$g(n)=\sum_{n|d}\mu(\frac dn)f(d)$$

关于 $\mathrm d$ 的高阶推导

二元

$$\mathrm d(AB)=\sum_{i|A}\sum_{j|B}[\gcd(i,j)=1]$$

三元

$$\mathrm d(ABC)=\sum_{i|A}\sum_{j|B}\sum_{k|C}[\gcd(i,j)=1][\gcd(j,k)=1][\gcd(i,k)=1]$$

n维二元

$$\sigma^k(AB)=\sum_{i|A}\sum_{j|B}[\gcd(i,\frac Bj)=1](ij)^k$$

n维三元

$$\sigma^k(ABC)=\sum_{i|A}\sum_{j|B}\sum_{l|C}[\gcd(i,\frac Bj)=1][\gcd(i,\frac Cl)=1][\gcd(j,\frac Cl)=1](ijl)^k$$

公式

常见技巧:变换枚举变量,在类欧几里得算法的时候也会用到.有点像二重积分三重积分那里使用一个变量去反卡另一个变量的值域,这个很难说清,需要自己做题理解一下.

常用公式:

$$[\gcd(i,j)=k]=[\gcd(\frac ik,\frac jk)=1]$$

• 反演结论1: $$[\gcd(i,j)=1]=\sum_{d|\gcd(i,j)}\mu(d)=\sum_{d|i,j}\mu(d)$$
• 结论2: 若 $f(n)=(1*g)(n)$ ,则 $g(n)=(\mu*f)(n)$ .
• 结论3:(1~n中与n互质的数的和是这个) $$\sum_{i=1}^{d}i[\gcd(i,d)=1]=\frac{\varphi(d)d}2$$

  结论3的证明:
  与d互质的数成对出现.
  若id互质则有d-i与d互质
  这样的数有$\frac{\varphi(d)d}2$对.

例题

1.求

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|\gcd(i,j)}\varphi(d)\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,j}\varphi(d)\\=&\sum_{d=1}^n\Big\lfloor\frac nd\Big\rfloor^2\varphi(d)\end{aligned}$$

第一步:一个数等于其因子的欧拉函数和,也就是 $\varphi=1*\mathrm{id}$ .
第二步:d如果是gcd的因子,则d一定同时是ij的因子.
第三步:改变枚举变量,先枚举d,考虑ij对于式子的贡献(这么想,假如d是d,i和j都可以是k*d,所以最大就是有 $\lfloor\frac nd\rfloor$ 个贡献,也就是这么多的 $\varphi(d)$ ,同时注意到后面式子完全和ij没关系了,放心转化即可.)

2.求

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\\=&\sum_{k=1}^{\min(m,n)}\sum_{i=1}^n\sum_{j=1}^mk[\gcd(i,j)=k]\\=&\sum_{k=1}^{\min(m,n)}\sum_{i=1}^n\sum_{j=1}^mk[\gcd(\frac ik,\frac jk)=1]\\=&\sum_{k=1}^{\min(m,n)}\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}k[\gcd(i,j)=1]\\=&\sum_{k=1}^{\min(m,n)}k\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}\sum_{d|\gcd(i,j)}\mu(d)\\=&\sum_{k=1}^{\min}k\sum_{d=1}^{\min}\mu(d)\Big\lfloor\frac n{kd}\Big\rfloor\Big\lfloor\frac m{kd}\Big\rfloor\\=&\sum_{T=1}^{\min}\Big\lfloor\frac n{T}\Big\rfloor\Big\lfloor\frac m{T}\Big\rfloor\sum_{k|T}k\mu(\frac Tk)\\=&\sum_{T=1}^{\min}\Big\lfloor\frac n{T}\Big\rfloor\Big\lfloor\frac m{T}\Big\rfloor\varphi(T)\end{aligned}$$

前三步是正常的推式子.
第四步上了反演结论.
第五步更换枚举变量消掉了两个 $\sum$ .
第六步使用T=kd代换,发现式子中的卷积关系.
第七步使用家喻户晓的 $\varphi=\mu*\mathrm{id}$ .

3.求

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)a_ia_j\\ =&\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]a_ia_j\\ =&\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[\gcd(i,j)=1]a_{di}a_{dj}\\ =&\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}\sum_{e|i,j}\mu(e)a_{di}a_{dj}\\ =&\sum_{d=1}^nd\sum_{e=1}^{n}\mu(e)\sum_{i=1}^{\lfloor\frac n{de}\rfloor}\sum_{j=1}^{\lfloor\frac n{de}\rfloor}a_{die}a_{dje}\\ =&\sum_{T=1}^n\sum_{d|T}d\mu(\frac Td)\sum_{i=1}^{\lfloor\frac n{T}\rfloor}\sum_{j=1}^{\lfloor\frac n{T}\rfloor}a_{iT}a_{jT}\\=&\sum_{T=1}^n\varphi(T)\left(\sum_{i=1}^{\lfloor\frac n{T}\rfloor}a_{iT}\right)^2\end{aligned}$$

直接预处理即可.

4.求

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\mathrm{lcm}(i,j)\\=&\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{\gcd(i,j)}\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^{\min}\frac{ij}{k}[\gcd(i,j)=k]\\=&\sum_{k=1}^{\min}\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}ijk[\gcd(i,j)=1]\\=&\sum_{k=1}^{\min}\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}ijk\sum_{d|\gcd(i,j)}\mu(d)\\=&\sum_{k=1}^{\min}k\sum_{d=1}^{\min(\lfloor\frac nk\rfloor,\lfloor\frac mk\rfloor)}d^2\mu(d)\sum_{i=1}^{\lfloor\frac n{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac m{kd}\rfloor}j\\=&\sum_{T=1}^{\min}T\sum_{d|T}d\mu(d)\sum_{i=1}^{\lfloor\frac nT\rfloor}i\sum_{j=1}^{\lfloor\frac mT\rfloor}j\end{aligned}$$

前两步正常化卷积式子.
第三步特别注意,因为ij除以k,所以后面要乘上一个k.
第四步反演结论.
第五步特别注意乘上$d^2$,因为枚举d的时候从1开始意味着ij还会发生值的变化.
第六步就是最终答案.使用方法就是,先证明T后面的函数是一个积性函数,然后线性筛算出来,T那一项直接前缀和算出来,最后两项是等差数列直接套公式求.

5.求

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^md(ij)\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|\gcd(x,y)}\mu(d)\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d=1}^{\min}\mu(d)[d|\gcd(x,y)]\\=&\sum_{d=1}^{\min}\mu(d)\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[d|\gcd(x,y)]\\=&\sum_{d=1}^{\min}\mu(d)\sum_{i=1}^n\sum_{j=1}^m\Big\lfloor\frac ni\Big\rfloor\Big\lfloor\frac mj\Big\rfloor[d|\gcd(i,j)]\\=&\sum_{d=1}^{\min}\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\Big\lfloor\frac n{id}\Big\rfloor\Big\lfloor\frac m{jd}\Big\rfloor\\=&\sum_{d=1}^{\min}\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\Big\lfloor\frac n{id}\Big\rfloor\sum_{j=1}^{\lfloor\frac md\rfloor}\Big\lfloor\frac m{jd}\Big\rfloor\end{aligned}$$

第一步是约数公式.
第二步是莫反.
第三步把条件提出来,让d的条件变成区间.
第四步提出来 $\mu$ .
第五步考虑xy的贡献是这么多直接乘进去.
第六步是消掉最后条件的,方法为直接枚举di和dj.
第七步是最后整理式子,程序中可以数论分块解决(后面的 $f$ 可以 $O(n)$ 预处理).

6.求

$$\begin{aligned}&\sum_{i=1}^n\mathrm{lcm}(i,n)\\=&n\sum_{d|n}\sum_{i=1}^n\frac id[\gcd(i,n)=d]\\=&n\sum_{d|n}\sum_{i=1}^{\frac nd}i[\gcd(i,\frac nd)=1]\\=&n\sum_{d|n}\sum_{i=1}^{d}i[\gcd(i,d)=1]\\=&n\sum_{d|n}\frac{\varphi(d)d}{2}\end{aligned}$$

第一步注意,因为n是固定的所以d不能从1开始,需要 $d|n$ .
第二步注意因为n是不变的,而i是变的,所以只需要乘一个n就可以.
第三步是因为,n|d,所以 $\frac nd\in d$ ,就有这个式子.
第四步就是结论3.
然后计算d phid:发现是积性函数,如果是质数结果是p(p-1)+1,如果不是质数对其进行因数分解:若 $p|i$ 则 $g(ip)=g(i)g(p)$ ,若不整除则 $g(ip)=g(i)+p^2(g(i)-g(i/p))$

7.求(f()是斐波那契数列第几项)

$$\begin{aligned}&\prod_{i=1}^n\prod_{j=1}^mf(\gcd(i,j))\\=&\prod_{k=1}^{\min}f(k)^{\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}[\gcd(i,j)=1]}\\=&\prod_{k=1}^{\min}f(k)^{\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}\sum_{e|\gcd(i,j)}\mu(e)}\\=&\prod_{k=1}^{\min}f(k)^{\sum_{e=1}^{\min(\lfloor\frac nk\rfloor,\lfloor\frac mk\rfloor)}\mu(e)\lfloor\frac n{ke}\rfloor\lfloor\frac m{ke}\rfloor}\\=&\prod_{T=1}^{\min}\prod_{k|T}f(k)^{\mu(\frac Tk)\lfloor\frac n{T}\rfloor\lfloor\frac m{T}\rfloor}\\=&\prod_{T=1}^{\min}\Big(\prod_{k|T}f(k)^{\mu(\frac Tk)}\Big)^{\lfloor\frac n{T}\rfloor\lfloor\frac m{T}\rfloor}\end{aligned}$$

第一步考虑斐波那契数列每一项对于答案的贡献(乘几次).
第二,三步莫反.
第四步是想把e的范围提出来,于是令T=ke,把T范围(其实就是原先e的范围)写在最下面.
第五步是解决方法:括号里的式子只与T有关,与nm无关,可以预处理,然后快速幂算出来结果加上去就可以了.

8.求

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k\\=&\sum_{i=1}^n\sum_{j=1}^m\Big(\sum_{d=1}^{\min} d[\gcd(i,j)=d]\Big)^k\\=&\sum_{d=1}^{\min}\sum_{i=1}^n\sum_{j=1}^md^k[\gcd(i,j)=d]\\=&\sum_{d=1}^{\min}d^k\sum_{x=1}^{\lfloor\frac{\min}d\rfloor}\mu(x)\Big\lfloor\frac n{dx}\Big\rfloor\Big\lfloor\frac m{dx}\Big\rfloor\\=&\sum_{T=1}^{\min}\Big\lfloor\frac n{T}\Big\rfloor\Big\lfloor\frac m{T}\Big\rfloor\sum_{d|T}d^k\mu(\frac Td)\end{aligned}$$

其中

$$\begin{aligned}f(n)=&\sum_{d|T}d^k\mu(\frac Td)\\=&\prod_{p_i}f(p_i^{x_i})\\=&\prod_{p_i}(p_i^{x_i}\cdot\mu(1)+p_i^{k(x_i-1)}\cdot\mu(p_i))\\=&\prod_{p_i}p_i^{k(x_i-1)}(p_i^k-1)\end{aligned}$$

第一步是常见展开环节.
第二步是把次方乘进去(注意不要认为就是例1的phi的次方)
第三步是莫反.
第四步是令T=dx,代换进去.
最后的式子左边是积性函数,也就直接线筛处理了,复杂度 $O(n+T\sqrt n)$ .
找规律: $f(4)=2^6*f(2)=f(2)*(f(2)+1),f(12)=f(4)*f(3)$

错误推法:

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k\\=&\sum_{i=1}^n\sum_{j=1}^m\Big(\sum_{d=1}^{\min}d[\gcd(i,j)=d]\Big)^k\\=&\sum_{d=1}^{\min}\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}(d[\gcd(i,j)=1])^k\\=&\sum_{d=1}^{\min}\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\Big(\sum_{e|\gcd(i,j)} d\mu(e)\Big)^k\\=&\sum_{d=1}^{\min}\sum_{e=1}^{\lfloor\frac{\min}{d}\rfloor}\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}( d\mu(e))^k\\=&\sum_{d=1}^{\min}\sum_{e=1}^{\lfloor\frac{\min}{d}\rfloor}\Big\lfloor\frac n{de}\Big\rfloor\Big\lfloor\frac m{de}\Big\rfloor(d\mu(e))^k\\=&\sum_{T=1}^{\min}\sum_{d|T}\Big\lfloor\frac n{T}\Big\rfloor\Big\lfloor\frac m{T}\Big\rfloor(d\mu(\frac Td))^k\\=&\sum_{T=1}^{\min}\sum_{d|T}\Big\lfloor\frac n{T}\Big\rfloor\Big\lfloor\frac m{T}\Big\rfloor\varphi^k(d)\end{aligned}$$

错因分析 :sum不可以随便提出来.默认 $(\sum\mu)^k=\sum(\mu^k)$ 这是不对的,根本就是两个函数.

9.计算

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\mathrm d(i)\mathrm d(j)\mathrm d(\gcd(i,j))\\=&\sum_{k=1}^{\min}\mathrm d(k)\sum_{i=1}^n\sum_{j=1}^m\mathrm d(i)\mathrm d(j)[\gcd(i,j)=k]\\=&\sum_{k=1}^{\min}\mathrm d(k)\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}\mathrm d(ik)\mathrm d(jk)[\gcd(i,j)=1]\\=&\sum_{k=1}^{\min}\mathrm d(k)\sum_{e|\gcd(i,j)}\mu(e)\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}\mathrm d(ik)\mathrm d(jk)\\=&\sum_{T=1}^{\min}\mathrm d(k)\mu(\frac Tk)\sum_{i=1}^{\lfloor\frac nT\rfloor}\sum_{j=1}^{\lfloor\frac mT\rfloor}\mathrm d(iT)\mathrm d(jT)\\=&\sum_{T=1}^{\min}\sum_{i=1}^{\lfloor\frac nT\rfloor}\mathrm d(iT)\sum_{j=1}^{\lfloor\frac mT\rfloor}\mathrm d(jT)\end{aligned}$$

第一步是枚举gcd.
第二步是除一个d.
第三步是莫反.
第四步是套路替换.
第五步是因为 $d*\mu=1$ ,直接消掉了.

10.计算

$$\begin{aligned}&\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{p=1}^{\lfloor\frac Nj\rfloor}\sum_{q=1}^{\lfloor\frac Nj\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1]\\=&\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{p=1}^{N}\sum_{q=1}^{N}[\gcd(i,j)=1][\gcd(p,q)=j]\\=&\sum_{i=1}^{N}\sum_{p=1}^{N}\sum_{q=1}^{N}[\gcd(i,p,q)=1]\\=&\sum_{i=1}^{N}\sum_{p=1}^{N}\sum_{q=1}^{N}\sum_{d|\gcd(i,p,q)}\mu(d)\\=&\sum_{d=1}^N\sum_{i=1}^{\lfloor\frac Nd\rfloor}\sum_{p=1}^{\lfloor\frac Nd\rfloor}\sum_{q=1}^{\lfloor\frac Nd\rfloor}\mu(d)\\=&\sum_{d=1}^N\mu(d)\left\lfloor\frac Nd\right\rfloor^3\end{aligned}$$

我们发现把j带回去能得到更好的效果…
于是剩下的就简单了,基本上是板题.

11.给一个数列 $a_n$ ,如果两个数之间的 $\gcd$ 不等于1那就有一条通路,现在求从1到n的通路有多少条.(998244353取模)

设dp[i]表示从1到i有多少条路.转移: $dp_i=\sum_{j=1}^{i-1}dp_j[\gcd(a_i,a_j)\neq1]$ ,初始化dp1=1,答案是dpn.

设 $s_i=\sum_{j=1}^idp_j$ ,上式转换成 $dp_i=s_{i-1}-\sum_{j=1}^{i-1}dp_j[\gcd(a_i,a_j)=1]$ ,莫反之后就是

$$dp_i=s_{i-1}-\sum_{j=1}^{i-1}dp_j\sum_{e|\gcd(a_i,a_j)}\mu(e)$$

怎么算这个式子呢?

开一个桶表示所有在i前面有这个因子的dp和,于是直接枚举因子然后乘上mu就行了…

12.计算

$$\begin{aligned} G(N)&=\sum_{n=1}^N\sum_{i=1}^n(-1)^i\gcd(n,i^2)\\ &=\sum_{i=1}^N(-1)^i\left(\sum_{n=i}^N\gcd(n,i^2)\right) \end{aligned}$$ $$\sum_{n=1}^N\gcd(n,i^2)=\sum_{d\mid i^2}\left\lfloor\dfrac{N}{d}\right\rfloor\cdot \left(\sum_{e\mid d}\mu\left(\dfrac{d}{e}\right)\cdot e\right)=\sum_{d\mid i^2}\left\lfloor\dfrac{N}{d}\right\rfloor\cdot\varphi(d)$$ $$\begin{aligned} G(N)&=\sum_{i=1}^N(-1)^i\left(\sum_{d\mid i^2}\varphi(d)\cdot \left(\left\lfloor\dfrac{N}{d}\right\rfloor-\left\lfloor\dfrac{i-1}{d}\right\rfloor\right)\right)\\ &=\sum_{d=1}^N\varphi(d)\left(\sum_{d\mid i^2}(-1)^i\cdot \left(\left\lfloor\dfrac{N}{d}\right\rfloor-\left\lfloor\dfrac{i-1}{d}\right\rfloor\right)\right) \end{aligned}$$

后半部分在筛法的时候可以累加.

一些比较牛逼的计算

1. 欧拉函数的定义:p是质数,有 $$\varphi(j)=j\cdot\prod_{p|j}\frac{p-1}{p}$$
2. 计算卷积 $\mathrm{id}*\varphi$ : 摆结论,由于直接分解即可,是 $O(\sqrt n)$ : $$n=p_1^{b_1}p_2^{b_2}...p_k^{b_k}$$ $$\mathrm{id}*\varphi(n)=n\prod_{i=1}^k\frac{b_ip_i-b_i+p_i}{p_i}$$ 缺点:一般积性函数计算,数论底子不扎实,化卷积式子(见题太少,紫题不满足需求了,建议来点黑的).

欧拉反演

$$n=\sum_{d|n}\varphi(d)$$

二项式反演

若有

$$f(x)=\sum_{i=x}\binom ixg(x)$$

则有

$$g(x)=\sum_{i=x}(-1)^{i-x}\binom ixf(x)$$

本质上是一个容斥式子,比如唱跳rap篮球.