\(\texttt{updating……}\)
多项式复合
对于多项式\(F(x),G(x)\)，其复合为:
\(F(G(x))=\sum_{i}[x^i]F(x)G(x)^i\)
求法：
设\(B=\sqrt n\)
\[\begin{aligned} \sum_{i=0}^n[x^i]F(x)G(x)^i &=\sum_{i=0}^{B-1}\sum_{j=0}^{B-1}[x^{iB+j}]F(x)G(x)^{iB+j}\\ &=\sum_{i=0}^{B-1}G(x)^{iB}\sum_{j=0}^{B-1}[x^{iB+j}]F(x)G(x)^j\\ \end{aligned} \]对于\(i\in [0,B-1]\)，预处理\(G(x)^i\)，复杂度\(O(n\sqrt n\log n)\)
\(\sum_{j=0}^{B-1}[x^{iB+j}]F(x)G(x)^j\)可以\(O(n^2)\)算，然后乘上前面的\(G(x)^{iB}\)就行了.
总复杂度\(O(n^2+n\sqrt n\log n)\)
多项式复合逆
对于多项式\(F(x)\)，存在另一多项式\(G(x)\)使得\(G(F(x))=x\)，则称\(G\)为\(F\)的复合逆。
可证明此时\(F(G(x))=x\)，即\(F\)与\(G\)互为复合逆。
拉格朗日反演
前提是0次项为0,1次项有逆。
对于函数\(F(x)\)及其复合逆\(G(x)\)有：
\[[x^n]G(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F(x)})^n \]证明略。
拉格朗日反演的应用
- \(\texttt{1.}\)多项式复合逆的求解
拉格朗日反演公式得:
\(F(x)\)的复合逆\(G(x)=\sum_{i=1}^n\frac{1}{i}[x^{i-1}](\frac{x}{F(x)})^ix^i\)
\[=\sum_{i=1}^n\frac{1}{i}[x^{i-1}](\frac{x}{F(x)})^{B\lfloor \frac{i}{B}\rfloor}(\frac{x}{F(x)})^{i\% B}x^i \]预处理 \((\frac{x}{F(x)})^{iB}\)以及\((\frac{x}{F(x)})^{i},i\in[0,B-1]\)
然后再合并就行了。
复杂度\(O(n^2+n\sqrt n\log n)\)
- \(\texttt{2.}\)P7592 数树（2021 CoE-II E）
简要题意
称一棵有根树\(T\)是\(k1-k2\)树，当且仅当其所有非叶节点满足子节点个数要么为\(k1\)要么为\(k2\)。
称一棵\(k1-k2\)树的权值是\(a\times k1\)的个数+\(b\times k2\)的个数。
节点无标号，但子树之间有顺序。
求随机生成的一棵树的期望权值。
解题思路
记\(F(x,y)\),\(x\)代表点数，\(y\)代表\(k1\)点数的二元生成函数。
枚举根节点是k1/k2/叶子，有：
\(F=x(yF^{k1}+F^{k2}+1)\)
\(\frac{F}{yF^{k1}+F^{k2}+1}=x\)
记\(G(x,y)=\frac{x}{yx^{k1}+x^{k2}+1}\)
则\(G\)与\(F\)互为复合逆。
由拉格朗日反演公式得：
\([x^n]F=\frac{1}{n}[x^{n-1}](yx^{k1}+x^{k2}+1)^n\)
\[\begin{aligned} [x^{n-1}y^m](yx^{k1}+x^{k2}+1)^n &=[x^{n-1}y^m]\sum_{i=0}^nC_n^i(yx^{k1}+x^{k2})^i\\ &=[x^{n-1}y^m]\sum_{i=0}^n\sum_{j=0}^iC_n^iC_i^j y^jx^{k1j+k2(i-j)}\\ &=[x^{n-1}]\sum_{i=0}^nC_n^iC_i^mx^{k1m+k2(i-m)}\\ &=\sum_{i=0}^nC_n^iC_i^m[k1m+k2(i-m)=n-1]\\ \end{aligned} \]\(i\)取值唯一，可以直接计算。
算出之后期望就很简单了。
复杂度\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int Pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
const int N = 1e7+7;
int fac[N],ifac[N];
void Init(int n)
{
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=Pow(fac[n],mod-2);
for(int i=n-1;i>=0;i--)
ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
if(n<0||m<0||n<m)return 0;
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
Init(N-1);
int k1,k2,n,a,b;
cin>>k1>>k2>>n>>a>>b;
int P=0,Q=0;
int I=Pow(n,mod-2);
for(int i=0;i*k1<=n-1;i++)
{
if((n-1-i*k1)%k2!=0)continue;
int j=(n-1-i*k1)/k2;
int S=1ll*C(n,i+j)*C(i+j,i)%mod;
S=1ll*S*I%mod;
Q=(Q+S)%mod;
int W=(1ll*a*i%mod+1ll*b*j%mod)%mod;
P=(P+1ll*S*W%mod)%mod;
}
Q=Pow(Q,mod-2);
cout<<1ll*P*Q%mod;
return 0;
}