反演与容斥
##反演
假设有两个函数\(f\)和\(g\)满足:\(f(n)=\sum_{k}a_{n,k}g(k)\),已知f求g的过程称为反演.
一般情况下,求反演只能高斯消元,但是有一些形式的反演有巧妙解法.
子集反演
一般形式: \[ f(S)=\sum_{T\subseteq S}g(T)\Leftrightarrow g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)\\ f(S)=\sum_{S\subseteq T\subseteq U}g(T)\Leftrightarrow g(S)=\sum_{S\subseteq T\subseteq U}(-1)^{|T|-|S|}f(T) \] 证明: \[ g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)\\ =(-1)^{|S|}\sum_{T\subseteq S}(-1)^{|T|}\sum_{P\subseteq T}g(P)\\ =(-1)^{|S|}\sum_{P\subseteq S}g(P)\sum_{T\subseteq S/P}(-1)^{|T|+|P|}\\ =(-1)^{|S|}\sum_{P\subseteq S}g(P)(-1)^{|P|}\sum_{T\subseteq S/P}(-1)^{|T|}\\ =(-1)^{|S|}\sum_{P\subseteq S}g(P)[S=P](-1)^{|P|}\\ =g(S) \]
不难发现,这个子集反演也就相当于在做高维前后缀和.
Example1(2019zrpzt七连day1D)
根据子集反演,设\(cnt_S\)为集合为\(S\)的数量,然后设\(f_S=\sum_{S'\subseteq S}cnt_{S'}\),有:\(ans=\sum_{S}2^{f_S}(-1)^{n-|S|}\).
做一遍高维前缀和就好,复杂度\(O(n2^n)\),应该也可以用分治FMT无脑做到\(O(n^22^n)\).
Example2(有标号DAG计数)
设\(f_{i,j}\)表示\(i\)个点,其中有\(j\)个点的入度数为\(0\)的方案数.(等一下,为撒子想到要记度数为\(0\)的点咧?因为你要一层一层转移,而在DAG中一层一层的就是零度点.而且说到底,你注意到有编号这个事实其实是很烦的,因为考虑如果一个一个点放上去,就有可能出现放的地方是等价的.而这么一层一层是绝对不会出现等价点的问题的.再说的仔细一点,如果我们把位置空着,然后选出一些放上来,是会出现等价点的问题的.但如果我们先选出来,然后再把边连上就不会.于是我们必须要枚举一些点然后再连到上面去)
这样我们每次枚举删去这\(j\)个点后,还剩下\(k\)个零度点.于是自然有: \[ f_{i,j}=\binom{i}{j}\sum_{k=1}^{i-j}(2^j-1)^k2^{j(i-j-k)}f_{i-j,k} \] 等一下咧,这复杂度\(O(n^3)\)了,这咋办啊?
好像转移优化不太了,因为\(k\)很难省去(在指数上).但我们注意到我们定义的时候说:\(0\)度点的数量恰好为\(k\),这个条件好像太强了果然OI就是发现限制太强了就弱一点,发现太弱了就强一点,所以我们想办法把它放弱一点.
一个经典的方法是:我们把定义改为至少\(k\)个零度点.但是这样转移好像还是不太行:零度点的情况太多了.那我们不妨考虑容斥,因为推导容斥的过程中,永远不害怕情况太多:我们直接考虑所有情况的集合.当然能不能推到最后是另一回事.
我们设\(f(n,S)\)表示\(n\)个点,其中只有\(S\)中的点的入度为\(0\);类似定义\(g(n,S)\)表示\(n\)个点,至少\(S\)中的点的入度为\(0\).显然我们所求也就是\(g(n,\empty)\),注意到: \[ g(n,S)=2^{|S|(n-|S|)}g(n-|S|,\empty)\\ g(n,S)=\sum_{S\subseteq T}f(n,T) \] 对第二个式子用子集反演,有: \[ f(n,S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(n,T) \] 接下来使用反复带入大法: \[ g(n,\empty)=\sum_{\empty\ne T}f(n,T)\\ =\sum_{T\subseteq S}(-1)^{|S|-|T|}g(n,S)\\ =\sum_{T\subseteq S}(-1)^{|S|-|T|}2^{|S|(n-|S|)}g(n-|S|,\empty)\\ =\sum_{m=1}^n\sum_{|T|=m}\sum_{T\subseteq S}(-1)^{|S|-|T|}2^{|S|(n-|S|)}g(n-|S|,\empty)\\ =\sum_{m=1}^n\binom{n}{m}\sum_{k=m}^n\binom{n-m}{k-m}(-1)^{k-m}2^{k(n-k)}g(n-k,\empty)\\ \] 可以发现:我们在推式子的过程中,将和集合本身有关的性质转化为了只和集合大小有关的式子,于是就简化了大量运算.
接下来我们继续化简: \[ \sum_{m=1}^n\binom{n}{m}\sum_{k=m}^n\binom{n-m}{k-m}(-1)^{k-m}2^{k(n-k)}g(n-k,\empty)\\ =\sum_{k=1}^n\sum_{m=1}^k\binom{n}{m}\binom{n-m}{k-m}(-1)^{k-m}2^{k(n-k)}g(n-k,\empty)\\ =\sum_{k=1}^n\binom{n}{k}2^{k(n-k)}g(n-k,\empty)\sum_{m=1}^k\binom{k}{m}(-1)^{k-m}\\ =\sum_{k=1}^n\binom{n}{k}2^{k(n-k)}g(n-k,\empty)((1-1)^k-(-1)^k)\\ =\sum_{k=1}^n\binom{n}{k}2^{k(n-k)}g(n-k,\empty)(-1)^{k-1}\\ \] 注意到复杂度已经降到\(O(n^2)\)了.
上面是从集合的角度一步步分析得到的.但如果你直接从容斥的角度考虑,忽略掉那个\((-1)^{k-1}\),把它当成一个可以数学归纳出来的容斥系数,那么这个式子会得到一个很简单的理解方式: \[ f_n=\sum_{k=1}^n\binom{n}{k}(-1)^{k-1}2^{k(n-k)}f_{n-k}\\ \] 也就是直接设,然后钦定其有至少\(j\)个,然后配容斥系数.
二项式反演
一般形式: \[ f(n)=\sum_{k=0}^nC_n^kg(k)\Leftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}C_n^kf(k)\\ f(n)=\sum_{k=0}^n(-1)^k\binom{n}{k}g(k)\Leftrightarrow g(n)=\sum_{k=0}^n(-1)^k\binom{n}{k}f(k)\\ f(n)=\sum_{k=n}^NC_k^ng(k)\Leftrightarrow g(n)=\sum_{k=n}^N(-1)^{k-n}C_k^nf(k)\\ f(n)=\sum_{k=n}^N(-1)^k\binom{k}{n}g(k)\Leftrightarrow g(n)=\sum_{k=n}^N(-1)^k\binom{k}{n}f(k)\\ \] 显然以\((-1)^ng(n)\)代替\(g(n)\)即可从第一个式子推导第二个式子,下面证明第一个式子: \[ g(n)=\sum_{k=0}^n(-1)^{n-k}C_n^kf(k)\\ =\sum_{m=0}^n\sum_{k=0}^{n-m}(-1)^kC_{n-m}^kC_n^mg(m)\\ =\sum_{k=0}^n(-1)^kC_n^k\sum_{m=0}^{n-k}C_{n-k}^mg(m)\\ =\sum_{k=0}^n(-1)^kC_n^kf(n-k)\\=\sum_{k=0}^n(-1)^{n-k}C_n^kf(k)\\ \]
Example1(错排问题)
\(n\)个有编号的人站成一排,求他们都没有站到自己编号对应位置的方案数.
设\(f(n)\)为\(n\)个人随便站的方案数,\(g(n)\)为\(n\)个人都站错的方案数.
如果知道\(g\)的表达式,我们可以通过枚举有多少人站错位置来得到\(f\),即:\(f(n)=\sum_{k=0}^nC_n^kg(k)\).
显然就是一个二项式反演,\(g(n)=\sum_{k=0}^n(-1)^{n-k}C_n^kf(k)=\sum_{k=0}^n(-1)^{n-k}C_n^kk!\).
值得一提的是,我们再观察一下最后得到的错排公式并进行一定的化简,可以得到:\(g(n)=n!\sum_{0\leq k\leq n}\cfrac{(-1)^k}{k!}\\\).
不难发现\(n!\)的后面形如\(e^{-1}\)的泰勒展开,我们考虑直接将泰勒展开的公式带入,可以得到: \[ g(n)=\cfrac{n!}{e}-n!\sum_{k>n}\cfrac{(-1)^k}{k!}\\ =\cfrac{n!}{e}-\cfrac{(-1)^{n+1}}{n+1}\sum_{0\leq k}(-1)^k\cfrac{(n+1)!}{(k+n+1)!} \] 用一些我不会的方法分析误差,会发现后面的项所能带来的误差很小,于是有\(g(n)=\lfloor\cfrac{n!}{e}+\cfrac{1}{2}\rfloor+[n=0]\).
另外,观察\(g\)关于\(f\)的表达式,不难求出\(g\)的递推式:\(g(n)=ng(n-1)+(-1)^n\).
下面证明\(g_n=(n-1)(g_{n-1}+g_{n-2})\),事实上,右边等于: \[ (n-1)(g_{n-1}+g_{n-2})\\ =(-1)^{n-1}(n-1)+(n-1)\sum_{k=0}^{n-2}((n-1)!\frac{(-1)^k}{k!}+(n-2)!\frac{(-1)^k}{k!})\\ =n!\sum_{k=0}^{n-2}\frac{(-1)^k}{k!}-(n-1)(-1)^n\\ \]
Example2(CF1750G)
如果没有字典序限制就是经典的二项式反演:考虑能被分为\(k\)段,说明有\(n-k\)个位置和前一个位置是大一的关系.我们钦定这些位置即可.
而有字典序限制也很经典,枚举LCP,枚举下一个位置,这个时候值域被分为若干个区间,假设剩了\(x\)个数字,\(y\)个区间,那么钦定\(j\)对的方案是\(\binom{x-y}{j}(x-j)!\).然后要乘上前面已经有了的,也就是乘上形如\((1+z)^k\).这样复杂度\(O(n^4)\).
这种问题通常LCP后的下一个位置都可以规避,这里你发现不同的取值只会让后面的\(x,y,k\)有\(O(1)\)种不同的取值,因此不用枚举.这样就是\(O(n^3)\).但是那个多项式乘法也可以规避,考虑最后的答案形如\(\sum (1+z)^kP_k(x)\),我们考虑写成\(P_{n-1}(z)+=(1+z)P_n(z)\),然后不断这么做,就只需要\(O(n^2)\).
Example3(CF1228E)
不妨设至多有\(i\)行\(j\)列最小值为\(1\)的答案是\(f_{i,j}\),恰好有\(i\)行\(j\)列最小值为\(1\)的答案是\(g_{i,j}\),注意到: \[ f_{n,m}=\sum_{i=0}^n\binom{n}{i}\sum_{j=0}^m\binom{m}{j}g_{i,j} \] 令\(h_{n,m}=\sum_{j=0}^m\binom{m}{j}g_{n,j}\\\),则\(f_{n,m}=\sum_{i=0}^n\binom{n}{i}h_{i,m}\\\),而\(f_{n,m}=k^{nm}(k-1)^{NM-nm}\).做两次二项式反演得到\(g\).
写到这里发现一个问题(其实是我发现问题后把上面原本写错的给改了),为啥\(f_{n,m}\ne \binom{N}{n}\binom{M}{m}k^{nm}(k-1)^{NM-nm}\)呢?我们写成子集反演形式看看: \[ f_{S,T}=\sum_{s\subseteq S}\sum_{t\subseteq T}g_{s,t}\\ f_{S,T}=\sum_{s\subseteq S}h_{s,T}\\ h_{S,T}=\sum_{t\subseteq T}g_{S,t}\\ \] 做子集反演: \[ f_{S,T}=k^{|S|\times |T|}(k-1)^{NM-|S||T|}\\ h_{s,T}=\sum_{S\subseteq s}(-1)^{|s|-|S|}f_{S,T}\\ g_{s,t}=\sum_{T\subseteq t}(-1)^{|t|-|T|}h_{s,T} \] 把集合改成集合大小就可以发现问题所在:
换句话说,\(g_{n,m}\)本身就包含了所有\(|S|=n,|T|=m\)的情况的和,并且在组合数\(\binom{m}{j}\)那里就找到了唯一确定的\(f_{s,t}\),因此\(f_{n,m}\)是唯一确定的.这意味着这里\(f\)的\(n,m\)并非集合之和,而是已经确定的集合的大小.
啥?这和我平常接触的二项式反演不一样啊?不说别的,第四题(BZOJ2839)的式子是这样的: \[ f_i=2^{2^{n-i}}\binom{n}{i}\\ f_k=\sum_{i=k}^n\binom{i}{k}g_i\\ g_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i \] 冷静一下,二项式反演的公式肯定没错,那也就一定是下面这几句出现了问题: \[ f_{n,m}=\sum_{i=0}^n\binom{n}{i}\sum_{j=0}^m\binom{m}{j}g_{i,j} \] 这个问题其实非常显然,我们的\(g_{i,j}\)定义为所有\(|S|=i,|T|=j\)的答案之和.\(f\)也是这么定义的,那这个式子就是错的,应该写成: \[ f_{n,m}=\sum_{i=0}^n\binom{N-i}{n-i}\sum_{j=0}^m\binom{M-j}{m-j}g_{i,j} \] 这样才是在不确定的那些行列中选择组合数,而不是在确定的那些行列中选.
但这样又有一个问题,就是这个题的特殊性,这个题要求\(g_{N,M}\),那此时\(g\)怎么定义不应该是一样的吗?
当然不一样,二项式反演讲究统一性,所有的定义必须遵循一个统一的原则,不然如果什么样子的函数都能反演,那一般的反演就不是一个需要解方程才能完成的东西了.
回到第四题,再看一遍这个式子: \[ f_k=\sum_{i=k}^n\binom{i}{k}g_i\\ \] 这个定义式就非常良性,\(g\)是已知的集合,\(f\)是未知的集合.我们乘上组合数就可以得到对于\(f\)来说已知的集合.因此这个就非常正确.
回到这个题上,为什么我们最后把\(f\)的定义改成\(f_{n,m}=k^{nm}(k-1)^{NM-nm}\)就对了呢?
再看看这个式子: \[ f_{n,m}=\sum_{i=0}^n\binom{n}{i}\sum_{j=0}^m\binom{m}{j}g_{i,j} \] 这个式子的右边在干这样一件事:那就是在已知\(n\)行\(m\)列的集合的前提下,从中选出\(i\)行\(j\)列并求\(g\).那么你从哪知道的\(n\)行\(m\)列呢?你得组合数啊!
所以,实际上的\(f\)是这样的: \[ f_{n,m}=\binom{N}{n}\binom{M}{m}\sum_{i=0}^n\binom{n}{i}\sum_{j=0}^m\binom{m}{j}g_{i,j}\\ f_{n,m}= \binom{N}{n}\binom{M}{m}k^{nm}(k-1)^{NM-nm} \] 好麻烦啊,能不能避免这种需要进一步思考集合意义的问题呢?
考虑二项式反演的第二个形式: \[ f(n)=\sum_{k=n}^NC_n^kg(k)\Leftrightarrow g(n)=\sum_{k=n}^N(-1)^{k-n}C_n^kf(k)\\ \] 不难发现这个式子无论怎么写,前后都一定是从已知集合中选东西.绝对不会出现上面的问题.
因此,我们重新写一下这个题的相关式子,考虑直接正难则反,设\(f'_{i,j}\)为至少有\(i\)行\(j\)列不满足条件的方案数,自然有\(f'_{i,j}=f_{N-i,M-j}\).你发现此时一定有: \[ f'_{n,m}=\sum_{i=n}^N\binom{i}{n}\sum_{j=m}^M\binom{j}{m}g'_{i,j} \] 最后答案就是\(g'_{0,0}\).
斯特林反演
一般形式: \[ f(n)=\sum_{k=0}^n\left\{ \begin{array}{c}n\\k\end{array} \right\}g(k)\Leftrightarrow g(n)=\sum_{k=0}^n\left[ \begin{array}{c}n\\k\end{array} \right](-1)^{n-k}f(k)\\ f(n)=\sum_{k=0}^n\left[ \begin{array}{c}n\\k\end{array} \right]g(k)\Leftrightarrow g(n)=\sum_{k=0}^n\left\{ \begin{array}{c}n\\k\end{array} \right\}(-1)^{n-k}f(k)\\ f(m)=\sum_{n=m}^M(-1)^{m-n}\left[ \begin{array}{c}n\\m\end{array} \right]g(n)\Leftrightarrow g(m)=\sum_{k=0}^M\left\{ \begin{array}{c}k\\m\end{array} \right\}f(k)\\ f(m)=\sum_{n=m}^M(-1)^{m-n}\left\{ \begin{array}{c}n\\m\end{array} \right\}g(n)\Leftrightarrow g(m)=\sum_{k=0}^M\left[ \begin{array}{c}k\\m\end{array} \right]f(k)\\ \] 考虑第一类斯特林数和第二类斯特林数的对称性,只需证明第一个和第三个式子即可.
反转公式: \[ \sum_{k=0}^n\left[ \begin{array}{c}n\\k\end{array} \right]\left\{ \begin{array}{c}k\\m\end{array} \right\}(-1)^{n-k}=\sum_{k=0}^n\left\{ \begin{array}{c}n\\k\end{array} \right\}\left[ \begin{array}{c}k\\m\end{array} \right](-1)^{n-k}=[m=n]\\ \] 第一个式子的证明: \[ g(n)=\sum_{m=0}^n[m=n]g(m)\\ =\sum_{m=0}^n\sum_{k=0}^n\left[ \begin{array}{c}n\\k\end{array} \right]\left\{ \begin{array}{c}k\\m\end{array} \right\}(-1)^{n-k}g(m)\\ =\sum_{k=0}^n\left[ \begin{array}{c}n\\k\end{array} \right](-1)^{n-k}\sum_{m=0}^k\left\{ \begin{array}{c}k\\m\end{array} \right\}g(m)=\sum_{k=0}^n\left[ \begin{array}{c}n\\k\end{array} \right](-1)^{n-k}f(k)\\ \] 第三个式子的证明: \[ g(m)=\sum_{n=m}^M[n=m]g(n)\\ =\sum_{n=m}^M\sum_{k=0}^M\left[ \begin{array}{c}n\\k\end{array} \right]\left\{ \begin{array}{c}k\\m\end{array} \right\}(-1)^{n-k}g(n)\\ =\sum_{k=0}^M\left\{ \begin{array}{c}k\\m\end{array} \right\}f(k)\\ \]
莫比乌斯反演
一般形式: \[ f(n)=\sum_{d|n}g(d)\Leftrightarrow g(n)=\sum_{d|n}\mu(\frac n d)f(d)\\ f(n)=\sum_{n|d}g(d)\Leftrightarrow g(n)=\sum_{n|d}\mu(\frac d n)f(d)\\ f(x)=\sum_{1\leq d}g(d)\Leftrightarrow g(x)=\sum_{1\leq d}f(\cfrac{x}d)\mu(d) \]
第一个式子的证明: \[ g(n)=\sum_{m|n}[\frac n m=1]g(m)\\ =\sum_{m|n}\sum_{d|\frac n m}\mu(d)g(m)\\ \] 注意到\([d|\frac n m]=[md|n]=[m|\frac n d]\\\). \[ g(n)=\sum_{d|n}\mu(d)\sum_{m|\frac n d}g(m)\\=\sum_{d|n}\mu(d)f(\frac n d)\\=\sum_{d|n}\mu(\frac n d)f(d)\\ \] 第二个式子的证明: \[ g(n)=\sum_{n|d}[\frac d n=1]g(d)\\=\sum_{n|d}\sum_{c|\frac d n}\mu(c)g(d)\\=\sum_{c|d}\sum_{nc|d}\mu(c)g(d)\\=\sum_{c}\mu(c)f(nc) \\=\sum_{n|d}\mu(\frac d n)f(d)\\ \] 第三个式子的证明: \[ \sum_{1\leq d}g(\cfrac{x}d)\mu(d)=\sum_{d\geq 1}\mu(d)\sum_{k\geq 1}f(\cfrac{x}{kd})\\ =\sum_{m\geq 1}f(\cfrac{x}{m})\sum_{d,k\geq 1}[m=dk]\mu(d)\\ =\sum_{m\geq 1}f(\cfrac{x}{m})\sum_{d|m}\mu(d)\\ =f(x) \]
Example1
求长度为\(n\)且仅包含小写英文字母且循环节长度恰为\(n\)的字符串个数.
不妨设\(f(n)\)表示长度为\(n\)的字符串个数,\(g(n)\)表示长度为\(n\)且循环节长度恰为\(n\)的字符串个数.
有\(f(n)=\sum_{d|n}g(d)\),根据莫比乌斯反演,\(g(n)=\sum_{d|n}\mu(\cfrac{n}{d})f(d)\).
Example2
求\(\sum_{i=1}^{n}\sum_{j=1}^mgcd(i,j)\\\).
我们通过这个题来讲一下推导技巧.
增加枚举量
\[ \sum_{i=1}^{n}\sum_{j=1}^mgcd(i,j)=\sum_{i=1}^n\sum_{j=1}^mid[gcd(i,j)]\\=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\varphi(d)\\ \]
交换枚举顺序
\[ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\varphi(d)=\sum_{d=1}^{\min(n,m)}\sum^{\lfloor\frac n d\rfloor}_{i=1}\sum^{\lfloor\frac m d\rfloor}_{j=1}\varphi(d)\\ \]
分离无关变量
\[ \sum_{d=1}^{\min(n,m)}\sum^{\lfloor\frac n d\rfloor}_{i=1}\sum^{\lfloor\frac m d\rfloor}_{j=1}\varphi(d)=\sum^{\min(n,m)}_{d=1}\varphi(d)\times\lfloor\cfrac n d\rfloor\times \lfloor\cfrac m d\rfloor\\ \]
考虑使用数论分块,只需处理出\(\varphi(d)\)的前缀和即可在\(O(\sqrt{n}+\sqrt{m})\)的复杂度解决此问题.
Example3
求\(\sum_{i=1}^{n}\sum_{j=1}^m[gcd(i,j)=1]\\\).
和上一道题几乎没区别,唯一不同的是需要处理的函数从\(id\)变为了\(\epsilon\).
Example4
求\(\sum_{i=1}^{n}\sum_{j=1}^m[gcd(i,j)\in prime]\\\).
考虑增加枚举量,则: \[ \sum_{i=1}^{n}\sum_{j=1}^m[gcd(i,j)\in prime]=\sum_{i=1}^{n}\sum_{j=1}^m\sum_{p\in prime}[gcd(i,j)=p]\\ =\sum_{p\in prime}\sum^{\lfloor\frac n d\rfloor}_{i=1}\sum^{\lfloor\frac m d\rfloor}_{j=1}[gcd(pi,pj)=p]\\ =\sum_{p\in prime}\sum^{\lfloor\frac n p\rfloor}_{i=1}\sum^{\lfloor\frac m p\rfloor}_{j=1}[gcd(i,j)=1]\\=\sum_{p\in prime}\sum_{d=1}^{\min(\lfloor\frac m p\rfloor,\lfloor\frac n p\rfloor)}\mu(d)\lfloor\cfrac n {pd}\rfloor\lfloor\cfrac m {pd}\rfloor\\ \] 于是转化为上一道题,但复杂度仍不可接受.
换元
考虑设\(x=pd\),则变为\(\sum_{x=1}^{\min(n,m)}\sum_{p\in prime\and p|x}\mu(\frac{x}{p})\lfloor\frac n {x}\rfloor\lfloor\frac m {x}\rfloor\\\).
####Example5([UR #5]怎样跑得更快)
首先先考虑去掉\(lcm\)使得式子中只有\(i,j,\gcd(i,j)\).
显然可以构造函数\(f(x)=x^{c-d},g(x)=x^d,h(x)=x^d\\\),然后将题目转化为\(\sum_{j=1}^nf(gcd(i,j))g(i)h(j)x_j\equiv b_i(\mod p)\\\).
\(\gcd(i,j)\)很难处理,于是考虑用莫比乌斯反演消掉.
可以求出\(f_r(n)\)使得\(f(n)=\sum_{d|n}f_r(d)\\\),也即\(f_r(n)=\sum_{d|n}\mu(\cfrac{n}{d})f(d)\).
则原式即: \[ \sum_{j=1}^n\sum_{d}[d|i][d|j]f_r(d)g(i)h(j)x_j\equiv b_i(\mod p)\\ \sum_{d|i}f_r(d)\sum_{j=1}^n[d|j]h(j)x_j\equiv \frac{b_i}{g(i)}(\mod p)\\ \] 令\(z_d=\sum_{j=1}^n[d|j]h(j)x_j\\\),有\(\sum_{d|i}f_r(d)z_d\equiv \frac{b_i}{g(i)}(\mod p)\\\).
这个也是一个莫比乌斯反演的形式,我们可以求出左边,进而求出\(z_d\).
而\(z_d=\sum_{j=1}^n[d|j]h(j)x_j=\sum_{d|j}^nh(j)x_j\),可以再次使用莫比乌斯反演求出\(h(j)x_j\),进而求\(x_j\).
无解条件显然是\(g_i=0\and x_i\ne 0\).
简而言之,这个题的步骤就是:
- 通过增加枚举量消掉\(lcm\)以及\(\gcd\)这些难以处理的项.
- 将\(i\)与\(j\)尽量分到式子两边.
- 先通过莫比乌斯反演求出一些值,再通过这些值反推.
Example6([CF1566H]Xor-quiz)
首先注意到一个重要的事实:我们只需要询问所有\(\mu(x)\ne 0\)的\(x\),就可以得到全部信息,而这些\(x\)的数量是完全足够我们全部询问一遍的.
注意到一个事实是,异或是模意义下的按位加减法,这意味着我们可以对异或做莫比乌斯反演.事实上,我们有: \[ f(n)=\bigoplus_{i\in A}i[\gcd(i,n)=1]\\ =\bigoplus_{i\in A}^ci\sum_{d|i,d|n}\mu(d)\\ \] 注意到\(\sum_{d|i}\mu(d)=\bigoplus_{d|i}|\mu(d)|\),于是: \[ f(n)=\bigoplus_{d|n}|\mu(d)|\bigoplus_{d|i,i\in A}i \] 接下来只要我们形式上写作\(n\),我们就默认\(\mu(n)\ne 0\),又令\(g(n)=\bigoplus_{n|i,i\in A}i\),此时自然有\(f(n)=\bigoplus_{d|n}g(d)\\\).这是一个经典的莫反形式,我们再反演回去就可以得到\(g(n)=\bigoplus_{d|n}\mu(\frac{n}{d})f(d)=\bigoplus_{d|n}f(d)\),也就是说我们可以求得所有的\(g(n)\),也就是这个集合中所有是\(n\)的倍数的异或值.
注意一个事实:如果我们设\(w(m)=\prod_{p\in prime,p|m}p\),那么我们就可以按照\(w\)的不同将所有数划分为若干个集合,每个集合在每次查询的时候要么都不被异或要么都被异或.这也告诉我们:我们只能求出每个集合中被选进\(A\)的这些数的异或值,而不能分开得知它们.接下来考虑如何知道这个,不妨设\(S(n)=\{x|w(x)=n\}\),又设\(h(n)=\bigoplus_{i\in A,i\in S(n)}i\).考虑用\(g(n)\)表示\(h(n)\),我们有: \[ g(n)=\bigoplus_{n|d}|\mu(\frac{d}{n})|h(d) \] 反演,有\(h(n)=\bigoplus_{n|d}g(d)\\\).于是我们可以求得所有的\(h(n)\)了.
现在的问题在于:对于数\(n,\mu(n)\ne 0\),我们要在\(S(n)\)中选出若干个数,使得它们的异或和为\(h(n)\),并且选出的数字总共有\(|A|\)个.
然后是根据数据随机,拿每个集合的线性基随机一下自由元,然后对着构造.多随机几次,最后做背包.
多重子集反演
设\(S\)为可重集合.
一般形式:定义\(\mu(S)\),若\(S\)包含重复元素则为\(0\),否则为\((-1)^{|S|}\). \[ f(S)=\sum_{T\subseteq S}g(T)\Leftrightarrow g(S)=\sum_{T\subseteq S}\mu(S-T)f(T)\\ \] 证明:
根据莫比乌斯反演,这个是显然的.
单位根反演(离散傅里叶变换)
一般形式(\(\omega_n=e^{\frac {2\pi i}{n}}\)): \[ f_m=\sum_{k=0}^{n-1}\omega_n^{mk}g_k \Leftrightarrow g_m=\frac 1 n\sum_{k=0}^{n-1}\omega_n^{-mk}f_k \] 可以发现这个式子其实就是FFT时所做的DFT与IDFT.
一般情况
考虑莫比乌斯反演的过程,我们实际上使用的是\([m|n]\sum_{d|\frac n m}\mu(d)=[n=m]\\\).
令\(c=md\),左边\(=\sum_{c|n}[m|c]\mu(\frac c m)=\sum([c|n])([m|c]\mu(\frac c m))\\\).
令\(A_{c,n}=[c|n]\),\(B_{m,c}=[m|c]\mu(\frac c m)\\\),那我们有\(BA=I\).
刚才的过程相当于: \[ Ax=b\\ x=Ix\\ x=(BA)x\\ x=B(Ax)\\ x=Bb\\ \] 无论是二项式反演还是莫比乌斯反演,他们都满足\(f(n)\)所依赖的\(g(k)\)有\(k\leq n\\\).
根据上面的情况,我们发现\(A\)是一个下三角矩阵,\(B\)是\(A^{-1}\).
现在来推导满足\(k\leq n\)的一般情况反演: \[ f(n)=\sum_{k=1}^na_{n,k}g(k)\\ \] 不妨设算子\(\mu(n,m)\),满足\(\sum_{k=1}^na_{n,k}\mu(k,m)=\sum_{k=1}^n\mu(n,k)a_{k,m}=[n=m]\\\). 即\(AB=BA=I\\\). \[ g(n)=\sum_{m=1}^n[n=m]g(m)\\=\sum_{m=1}^n\sum_{k=1}^n\mu(n,k)a_{k,m}g(m)\\=\sum_{k=1}^n\mu(n,k)f(k)\\ \] 由上我们发现,反演解决了一些在下标上的二元运算卷积: \[ c_r=\sum_{p,q}[f(p,q)=r]a_pb_q\\ \] 而我们需要把\(f\)分成两个独立的部分,通常正变换一下,处理一下,逆变换回来.
##容斥
一般形式
即:将求并集中元素个数转化成了求交集中元素个数.
我们有:\(\mid \bigcup_{i=1}^nS_i \mid=\sum_{T\subseteq \{1,...,n\}}(-1)^{|T-1|}\mid\bigcap_{p\in T}S_p \mid\).
证明:我们考虑对于每个元素,看它对最终答案的贡献.假设它所属\(m\)个集合\(T_1,...,T_m\),而除了这些集合以外的集合, \[ cnt=\sum_{i=1}^m(-1)^{i-1}\binom{m}{i}\\ =\binom{m}{0}-\sum_{i=0}^m(-1)^i\binom{m}{i}\\ =1-[m=0] \] 显然,当这个元素被包含的时候,贡献为\(1\),反之贡献为\(0\).
如果我们定义一类在集合上的函数\(F(S)=\sum_{p\in S}F(p)\),那么自然也有: \[ F(\bigcup_{i=1}^nS_i)=\sum_{T\subseteq \{1,...,n\}}(-1)^{|T|-1}F(\bigcap_{p\in T}S_p) \]
另外,我们上面的做法是:当交集好求时求并集.我们还可以使用一步补集转化: \[ \mid\bigcap_{i=1}^nS_i\mid=|U|-\mid\bigcup_{i=1}^n \overline{S_i}\mid \] 这样我们同样可以在并集好求的时候求交集.
会发现容斥和二项式反演是很像的.但是不一样的是,容斥是从集合的角度考虑,更注重单个元素的贡献;二项式反演是从函数的角度考虑,更关注函数之间的转化.
Example1(不定方程非负整数解计数)
考虑不定方程\(\sum_{i=1}^nx_i=m\),和\(n\)个限制条件\(x_i\leq b_i\),其中\(m\)和\(b_i\)都是非负整数,求该方程的非负整数解的数目.
首先,我们需要找出全集\(U\),以及刻画\(U\)中元素的\(P_i\)(条件):
- \(U\)是满足\(\sum_{i=1}^nx_i=m\)的所有非负整数解;
- 对于每个变量\(i\),都对应一个\(P_i=[x_i\leq b_i]\).
设所有满足\(P_i\)的解构成集合\(S_i\),那么我们需要求解的值就是\(\mid\bigcap_{i=1}^nS_i\mid\).而\(\mid U\mid\)显然是\(\binom{m+n-1}{n-1}\).我们有:\(\mid \bigcap_{i=1}^nS_i\mid=|U|-\mid\bigcup_{i=1}^n\overline{S_i}\mid\).考虑对\(\mid\bigcup_{i=1}^n\overline{S_i}\mid\)使用容斥原理,注意到\(\overline{S_i}\)的意义是满足\(x_{i}\geq b_{i}+1\)的解的数目.换句话说也就是部分变量有下界限制,那直接左右两边同时减去下界即可.于是枚举子集即可实现.
欸,等一下,咋想到的补集转化,又是咋想到要用容斥的捏?
我们冷静一下,首先补集转化和容斥都是一个思想:正难则反.我们要求满足条件的个数,就先想一下能不能求不满足条件的个数,然后拿总的个数减去.然后注意到不满足条件的意义是:有至少一个不满足,这样就很可以容斥了.
Example2(错排问题)
我们考虑从容斥的角度再次认识一下错排.
首先,我们需要找出全集\(U\),以及刻画\(U\)中元素的\(P_i\)(条件):
- \(U\)是长度为\(n\)的所有排列;
- 对于每个变量\(i\),都对应一个\(P_i=[p_i\ne i]\).
注意到所求仍然是\(\mid\bigcap_{i=1}^nS_i\mid\).于是我们仍然试图\(|\bigcap_{k=1}^m\overline {S_{a_k}}|\).考虑其意义,也即:有\(m\)个位置被确定了,而其它位置没有限制,于是\(|\bigcap_{k=1}^m\overline {S_{a_k}}|=\binom{n}{m}(n-m)!\).根据容斥,自然有:\(d_n=n!-\sum_{m=1}^n(-1)^{m-1}\binom{n}{m}(n-m)!=n!\sum_{m=0}^n\cfrac{(-1)^m}{m!}\).
Example3(bzoj3622已经没有什么好害怕的了)
首先可以用dp+双指针得到\(f_i\)表示勒令\(i\)对满足条件的方案数.把\(k\)的定义改为恰好\(k\)对满足条件的显然是同强度的.
我们接下来仍然考虑容斥,首先,我们需要找出全集\(U\),以及刻画\(U\)中元素的\(P_i\)(条件).
等一下,这个好像不好刻画?
我们先回归一下容斥的本质:考虑每个元素的贡献.注意到恰好\(a\)对的方案会被恰好\(b\)对的方案计算\(\binom{b}{a}\)次.我们再考虑一种方式理解容斥:我们一步一步把正确的答案消出来:简单来说,我第一步让所有恰好为\(k\)的方案贡献为\(1\),其它的可能也有贡献,但我们忽略他们.第二步让所有恰好为\(k+1\)的方案贡献为\(0\),第三步以此类推.于是这个题,我们考虑也这么做:这样第一步令\(ans=f_k\),第二步除去其中被多算的\(k+1\),这一步令\(ans-=\binom{k+1}{k}f_{k+1}\).这个时候,我们再考虑\(k+2\)的贡献:它将在\(f_k\)时贡献\(\binom{k+2}k\)次,在\(f_{k+1}\)时贡献\(-\binom{k+2}{k+1}\binom{k+1}{k}=-\binom{k+2}{k}\binom{2}{1}\)次,那它现在的贡献还有:\(-\binom{k+2}k\)次.以此类推,可以得到\(ans=\sum_{i=k}^nf_i(-1)^{i-k}\binom{i}{k}\).
等一下,这也太麻烦了,就不能从集合的角度分析嘛?
冷静一下,如果我们要做容斥,我们必须考虑每个元素单独的贡献,但是在这个题中,每个元素并没有单独的贡献,而是整个集合需要满足性质才能贡献.也就是说,我们无法分析每个\(P_i\).而考虑集合就需要将集合分类,从而使用二项式反演.
换句话说,这个定义在集合上的函数并不满足可加性.
换句话说,我们要用容斥,就一定要刻画\(P_i\),因为只有这个时候,我们才能通过分析满不满足\(P_i\)的解集的交并来实现.
再换句话说,大部分的所谓的容斥其实都和集合没啥关系,我们做容斥就是需要逐个考虑贡献,把它们贡献全都杀成\(1/0\)就行.
Example4(HAOI2008硬币购物)
如果直接对于每次询问暴力做,复杂度显然是\(O(4ns)\),无法接受.于是考虑预处理来降低单词询问复杂度.
注意到硬币数量很少,并且每个硬币的贡献可以独立计算.我们完全可以刻画\(P_i=[use_i\leq d_i]\),从而可以用容斥做.复杂度\(O(4m+n2^4)\).
Example5
Alice和Bob在玩游戏,他们有一个\(n\)个点的无向完全图,设所有的边组成了集合\(E\),他们想取遍\(E\)的所有非空子集,对某个集合\(S\)有一个估价\(f(S)\):考虑\(n\)个点与\(S\)中的边组成的图,我们用\(m\)种颜色对所有点染色,其中同一个连通块的点必须染成一种颜色,那么\(f(S)\)等于这个图的染色方案数.同时,Alice喜欢奇数,所以当\(|S|\)为奇数时,Alice的分值加上\(f(S)\),否则Alice的分值减去\(f(S)\),求最后的分值.\((n,m\leq 10^6)\).
一开始抄题的时候没有写染色而是直接写”设\(k\)为连通块个数,则\(f(S)=m^k\).”然后发现做不了,因为\(|S|\)相同的\(f(S)\)不尽相同,而且可能情况还蛮多的.冷静一下,注意到连通块这个性质太强了:如果我们把它放到指数上,那应该会做得很痛苦.所以我们考虑每有一个连通块就乘上一个\(m\),这个看上去就简单一些.
但是这样好像还是不太好做,毕竟现在我们面对的还是一个难以转化为计数问题的图论问题,只是把问题的单位元素从图变成了连通块.那我们能不能再进一步:把单位元素换成单点呢?
考虑由于连通块要染一种颜色,那\(x\leftrightarrow y\Rightarrow col_x=col_y\).注意到这是一个单位元素更小的限制条件!并且我们发现我们将与\(-1\)有关的单位元素(从一开始就是点)和与\(f\)有关的单位元素统一起来了.这也提示我们做计数的时候,尤其是做容斥的计数的时候,最好先将单位元统一,这样后面才可能更容易做.
接下来就可以写式子了,令\(F(C)\)表示在\(C\)情况下的染色方案,\(T_{(i,j)}\)表示满足边\((i,j)\)限制的解集: \[ ans=\sum_{\empty\ne S\subseteq E}(-1)^{|S|-1}F(\bigcap_{(i,j)\in S}T_{(i,j)}) \] 冷静一下!这个东西和容斥长得那叫一个一模一样啊.我们看看能不能逆向分析出\(ans\)的意义:显然是\(F(\bigcup_{i=1}^{m}P_i)\).也就是完全图中至少有两个点颜色相同的染色数.根据补集转化,我们只需求出两两点不相同的染色数即可.所以最后的答案就是\(m^n-m^{\underline{n}}\).
Example6
求\(\varphi(n)\).
考虑这么一个事实:假设\(n=\prod p_i^{q_i}\),注意到令\(P_i=[\gcd(i,n)=1]\),我们所求也就是\(\mid\bigcap_{i=1}^nS_i\mid\).于是可以用上面的方法做.另外,这里的做法引出莫比乌斯反演.
Example7(AGC058D)
直接容斥好像不太可做,我们把容斥中的条件改为有多少个极长的形如\(ABCABCAB...\)这样的串.
乍一看这个极长的条件好像巨难满足,但实际上我们冷静一下,我们只需要满足这个串长度大于等于\(3\)并且开头不能往前延申就可以了,后面其实是没啥必要管的.
拿组合数算一算.
Example8(AGC035F)
显然问题只在于重复计算的问题.我们先将所有状态做一个双射:对于一个网格,唯一可能被重复计算的只可能是一个拐角的\(1\),我们让这种情况下的行尽可能长.
然后捏?注意到这样的话一个拐角的角一定是行了,是列就一定不合法,我们考虑把不合法的列杀了.
于是做一下容斥,答案是\(\sum_{i=0}^{\min(n,m)}(-1)^i\binom{n}{i}\binom{m}{i}i!(m+1)^{n-i}(n+1)^{m-i}\).
Example9
给定若干个限制条件\((x,y)\),表示\(a_x=y\)和\(a_y=x\)必须满足至少一个,求排列方案数.
首先\(i\rightarrow p_i\)把排列转化成图,这样上面的限制条件也就是有一些无向的链和环,最后定向.一开始以为随便做做,思考一下注意到如果有长度为\(2\)的链,它自己成环的话是不用\(\times 2\)的.
这咋办.一个办法是:我们考虑容斥,先随便放进去,最后再钦定若干个自己成环.诶等一下为啥这个容斥是对的?因为系数是\(\times 2\),所以一个有\(1\)个单独成环的状态会被随便放的情况恰好多算一次.类似可以做容斥.
当然,也可以考虑先把其它的合并,最后做长度为\(2\)的链,但是!一开始一定要钦定有序,最后再用组合数统一算答案.因为一开始带着顺序做很难做.
Example10([AGC036F] Square Constraints)
由题意得:\(n^2-i^2\leq P_i^2\leq (2n)^2-i^2\).
当一个东西有上界又有下界的时候可以想到容斥.问题转化为只有上界.假设最后所有的上界为\(l_i\),那么只有上界的答案应该是什么呢?将\(l\)从小到大排序,答案就是\(\prod_{i=0}^{2n-1}(l_i-i)\).(注意到必须满足\(l_{2n-1}=2n-1\).)
但是这个东西和容斥怎么结合起来呢?我们将限制放到二维平面上,注意到上下界的限制其实是两个\(\frac{1}4\)的圆弧.而通过圆弧的性质不难看出:最终的\(l\)分为三部分:在下半部分圆弧上的,在上半部分圆弧后面的,在上半部分圆弧前面的.而如果想知道\(l\)按照顺序排序,我们只需要对前两部分做归并,然后将最后一部分直接放到后面即可.于是我们考虑按照\(l\)的大小为顺序进行一个类似归并的东西,每次判断当前下半部分圆弧是否要往上加点即可.这样我们可以处理前两部分对答案的贡献,但问题在于第三部分对答案的贡献怎么做,我们需要找到第三部分上的点在排序后的位置.我们预先枚举容斥集合的大小即可,这样就可以快速算出这个东西,于是复杂度\(O(n^3)\).
Example11([23省选第一轮集训day4]C带劲的旅行)
(下面将\(n\)和\(m\)反着写)
设\(p=\frac{2k}{n},q=n-p\).
首先注意到期望\(=P[len\geq 1]+P[len\geq 2]+\cdots\).
考虑如何计算\(P[len\geq x]\),如果我们设\(a_i\)表示以\(i\)作为开头的极长的带劲的长度大于等于\(x\)的序列的集合,那么最后无非是要求所有\(a\)的并.考虑用容斥做到求所有\(a\)的交.不过要注意讨论一下是不是第一个点.
Example12
给定\(n,k\)和\(n\)个点各自的颜色,对有编号无根树计数,要求相同颜色组成的连通块大小不超过\(k\).\(n\leq 300\).
著名结论:\(n\)个点\(m\)个连通块任意连边成树的方案数是\(n^{m-2}\prod s\),其中\(s\)是每个连通块的大小.但是,如果我们强行对每种颜色分成若干连通块,我们要防止它们之间有边.这就是我一开始没做出来的原因:要容斥的根本不是树的大小不能超过\(k\),由于树的形态多变,这个是不能维护的!正确的做法是找到若干个相同颜色的大小小于等于\(k\)的连通块,要求它们两两无边.甚至根本就不是它们可以连边但是大小不能超过\(k\),我们要容斥的东西一定要好算,简单.
然后就做完了,每次暴力合并若干个颜色相同的块,容斥系数\((-1)^{块数-1}\).
容斥是一个层层递进的东西,我们每一步都是基于上一步的限制:它本身就是一个求解集的东西.
Min-Max容斥
对于: \[ \mid \bigcup_{i=1}^nS_i \mid=\sum_{T\subseteq \{1,...,n\}}(-1)^{|T-1|}\mid\bigcap_{p\in T}S_p \mid \] 考虑一个特例:\(S_i=\{1,2,\cdots,a_i\}\),那么上面的式子导出min-max容斥(我们设\(S=\{a_1,a_2,\cdots,a_n\}\))(第二个式子可以把前缀改成后缀): \[ \max(S)=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-1}\min(T)\\ \min(S)=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-1}\max(T) \] 由于是集合,这个式子在期望意义下同样成立: \[ E(\max\{S\})=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-1}E(\min\{S\})\\ E(\min\{S\})=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-1}E(\max\{S\}) \] 进一步,这个式子可不止能求min-max的转化,它可以求出集合中第k大的数字: \[ kth\max\{S\}=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min\{T\}\\ kth\min\{S\}=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max\{T\}\\ E(kth\max\{S\})=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min\{T\})\\ E(kth\min\{S\})=\sum_{T\subseteq S,T\ne \empty}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\max\{T\}) \] 原理是消掉前\(k-1\)大的数字,让他们的贡献为\(0\),剩下的配一下容斥系数.
Example1([23省选10连测 day6]A)
不妨设\(tim_i\)为\([i,i+1]\)第一次被覆盖的时间,答案就是: \[ E(\max_{i=1}^{n-1}\{tim_i\})=\sum_{T\subseteq \{1,2,\cdots,n-1\},T\ne \empty}(-1)^{|T|-1}E(\min_{j\in T}\{tim_j\}) \] 设\(f(S)\)为有多少个区间能覆盖至少一个\([i,i+1],i\in S\),考虑\(E=p_{[t\geq 0]}+p_{[t\geq 1]}+p_{[t\geq 2]}+\cdots\),于是\(E(\min_{j\in S}\{tim_j\})=\frac{m}{f(S)}\).
于是: \[ ans=\sum_{T\subseteq \{1,2,\cdots,n-1\},T\ne \empty}(-1)^{|T|-1}f(T)\\ =\sum_{k=0}^m\frac{m}{k}\sum_{T\subseteq \{1,2,\cdots,n-1\},T\ne \empty,f(T)=k}(-1)^{|T|-1} \] 注意到\(f(S)\)可能不那么好求,我们求\(g(S)=m-f(S)\),也就是不包含任何一个\([i,i+1],i\in S\)的区间个数,我们有: \[ ans=\sum_{k=0}^m\frac{m}{m-k}\sum_{T\subseteq \{1,2,\cdots,n-1\},T\ne \empty,g(T)=k}(-1)^{|T|-1} \] 这里已经不难写出\(O(n^3)\)的dp了.
那么怎么优化呢?设\(dp_{i,j}\)表示只考虑\([1,i]\)时(\([i-1,i]\)必选),\(\sum_{g(T)=j}(-1)^{|T|-1}\)的答案,不难发现每次加入一个区间\([l,r]\)就会让\(dp_{i,j},i<=l\)对\(dp_{r,j+1}\)的贡献乘一个\(1\).
如何处理这个事情?我们用类似多项式的东西,前者相当于平移多项式系数,后者相当于标量乘法,然后拿线段树维护和,复杂度\(O(nm\log n)\).
反射容斥
一般形式:给定二维平面上两个点\(S\)和\(T\),其中\(T\)在\(S\)的右方,给定两条线\(y=a\)和\(y=b\),每次可以向右上或者右下走一步,求不碰线的从\(S\)到\(T\)的方案数.
我们不妨设\(A\)表示一定碰了一次上界的方案数,\(B\)表示一定碰了一次下界的方案数,\(AB\)表示一定碰了一次上界后碰了一次下界的方案数……
最后的答案就是随便走\(-A-B+AB+BA-ABA-BAB...\).
考虑设步数为\(n\),那显然长度最多为\(\cfrac{n}{a-b}\).