创建一个网站要多少钱,定制自动化营销,网站开发用php好吗,一个服务器可以放多少网站众所周知#xff0c;对于有标号计数的指数型生成函数 f(x)f(x)f(x)#xff0c;将其任意地进行无顺序的组合#xff0c;得到的生成函数是exp(f(x))exp(f(x))exp(f(x))。
而对于无标号计数的这样的组合#xff0c;我们就需要引入一个叫 Eular\text{Eular}Eular 变换的东西 E…众所周知对于有标号计数的指数型生成函数 f(x)f(x)f(x)将其任意地进行无顺序的组合得到的生成函数是exp(f(x))exp(f(x))exp(f(x))。
而对于无标号计数的这样的组合我们就需要引入一个叫 Eular\text{Eular}Eular 变换的东西 E(f(x))\mathcal{E}(f(x))E(f(x))
这个符号打法\mathcal(E)
为了方便本文中记fif_ifi表示[xi]f(x)[x^i]f(x)[xi]f(x)。两种表述可能混用。
我们先引入一个实际问题nnn个点无标号有根树的计数。两棵树被认为相同当且仅当存在一种重标号方案使得它们的根标号相同且边集相等。
对于一棵树我们去掉它的根然后就分成若干棵独立的子树。所以对无标号有根树的OGF\text{OGF}OGF F(x)F(x)F(x)有
F(x)x⋅E(F(x))F(x)x\cdot\mathcal E(F(x))F(x)x⋅E(F(x))
先思考这个问题的主要矛盾在什么地方对于分出来的若干子树如果有一些子树完全一致那么它们只会贡献一次方案。但如果只是大小相同而本质不同仍然算作不同的方案。
换句话说最终的方案只和每种本质不同的子树使用的个数有关。考虑背包。
对每种本质不同的大小为kkk的树构造完全背包的生成函数即
11−xk\frac{1}{1-x^k}1−xk1
那么我们可以得到一个简单粗暴的定义式
E(F(x))∏i1∞1(1−xi)Fi\mathcal E(F(x))\prod_{i1}^{\infin}\frac 1{(1-x^i)^{F_i}}E(F(x))i1∏∞(1−xi)Fi1
FiF_iFi是因为有FiF_iFi种本质不同大小为iii的物品
然后开始愉快地推式子
G(x)E(F(x))∏i1∞1(1−xi)FiG(x)\mathcal E(F(x))\prod_{i1}^{\infin}\frac 1{(1-x^i)^{F_i}}G(x)E(F(x))i1∏∞(1−xi)Fi1
既然有连乘先求个ln\lnln
ln(G(x))−∑i1∞Filn(1−xi)\ln (G(x))-\sum_{i1}^{\infin}F_i\ln(1-x^i)ln(G(x))−i1∑∞Filn(1−xi)
ln\lnln还是看不顺眼求个导
G′(x)G(x)∑i1∞Fiixi−11−xi\frac{G(x)}{G(x)}\sum_{i1}^{\infin}F_i\frac{ix^{i-1}}{1-x^i}G(x)G′(x)i1∑∞Fi1−xiixi−1
又看见了喜闻乐见的完全背包直接展开
G′(x)G(x)∑i1∞Fi⋅ixi−1∑j0∞xij\frac{G(x)}{G(x)}\sum_{i1}^{\infin}F_i\cdot ix^{i-1}\sum_{j0}^{\infin}x^{ij}G(x)G′(x)i1∑∞Fi⋅ixi−1j0∑∞xij
G′(x)G(x)∑i1∞Fi⋅i∑j0∞xi(j1)−1\frac{G(x)}{G(x)}\sum_{i1}^{\infin}F_i\cdot i\sum_{j0}^{\infin}x^{i(j1)-1}G(x)G′(x)i1∑∞Fi⋅ij0∑∞xi(j1)−1
G′(x)G(x)∑i1∞Fi⋅i∑j1∞xij−1\frac{G(x)}{G(x)}\sum_{i1}^{\infin}F_i\cdot i\sum_{j1}^{\infin}x^{ij-1}G(x)G′(x)i1∑∞Fi⋅ij1∑∞xij−1
再积分回来
ln(G(x))∑i1∞Fi⋅i∑j1∞xijij\ln(G(x))\sum_{i1}^{\infin}F_i\cdot i\sum_{j1}^{\infin}\frac{x^{ij}}{ij}ln(G(x))i1∑∞Fi⋅ij1∑∞ijxij
整理一下
ln(G(x))∑i1∞Fi∑j1∞xijj\ln(G(x))\sum_{i1}^{\infin}F_i\sum_{j1}^{\infin}\frac{x^{ij}}jln(G(x))i1∑∞Fij1∑∞jxij
ln(G(x))∑j1∞1j∑i1∞Fixij\ln(G(x))\sum_{j1}^{\infin}\frac 1j\sum_{i1}^{\infin}F_ix^{ij}ln(G(x))j1∑∞j1i1∑∞Fixij
ln(G(x))∑j1∞F(xj)j\ln(G(x))\sum_{j1}^{\infin}\frac{F(x^j)}jln(G(x))j1∑∞jF(xj)
ln(G(x))∑i1∞F(xi)i\ln(G(x))\sum_{i1}^{\infin}\frac{F(x^i)}iln(G(x))i1∑∞iF(xi)
得到 Eular\text{Eular}Eular 变换的计算式雾
E(F(x))exp(∑i1∞F(xi)i)\mathcal E(F(x))\exp(\sum_{i1}^{\infin}\frac{F(x^i)}{i})E(F(x))exp(i1∑∞iF(xi))
然后回到原问题
F(x)x⋅E(F(x))F(x)x\cdot\mathcal E(F(x))F(x)x⋅E(F(x))
F(x)x⋅exp(∑i1∞F(xi)i)F(x)x\cdot \exp(\sum_{i1}^{\infin}\frac{F(x^i)}{i})F(x)x⋅exp(i1∑∞iF(xi))
两边求导(如果高数不好建议自己多写几步)
F′(x)exp(∑i1∞F(xi)i)x⋅exp(∑i1∞F(xi)i)⋅∑i1∞ixi−1⋅F′(xi)iF(x)\exp(\sum_{i1}^{\infin}\frac{F(x^i)}{i})x\cdot \exp(\sum_{i1}^{\infin}\frac{F(x^i)}{i})\cdot\sum_{i1}^{\infin}\frac{ix^{i-1}\cdot F(x^i)}iF′(x)exp(i1∑∞iF(xi))x⋅exp(i1∑∞iF(xi))⋅i1∑∞iixi−1⋅F′(xi)
F′(x)exp(∑i1∞F(xi)i)F(x)∑i1∞xi−1⋅F′(xi)F(x)\exp(\sum_{i1}^{\infin}\frac{F(x^i)}{i})F(x)\sum_{i1}^{\infin}x^{i-1}\cdot F(x^i)F′(x)exp(i1∑∞iF(xi))F(x)i1∑∞xi−1⋅F′(xi)
两边同时乘上xxx
x⋅F′(x)F(x)F(x)∑i1∞xi⋅F′(xi)x\cdot F(x)F(x)F(x)\sum_{i1}^{\infin}x^i\cdot F(x^i)x⋅F′(x)F(x)F(x)i1∑∞xi⋅F′(xi)
#undef G
记
G(x)∑i1∞xi⋅F′(xi)G(x)\sum_{i1}^{\infin}x^i\cdot F(x^i)G(x)i1∑∞xi⋅F′(xi)
x⋅F′(x)F(x)F(x)G(x)x\cdot F(x)F(x)F(x)G(x)x⋅F′(x)F(x)F(x)G(x)
考虑求这东西的第xnx^nxn项
nFnFn∑k1n−1FkGn−knF_nF_n\sum_{k1}^{n-1}F_kG_{n-k}nFnFnk1∑n−1FkGn−k
Fn1n−1∑k1n−1FkGn−kF_{n}\frac 1{n-1}\sum_{k1}^{n-1}F_kG_{n-k}Fnn−11k1∑n−1FkGn−k
如果我们知道GGG就可以直接分治 NTT 算出FFF
现在考虑这个GGG
G(x)∑i1∞xi⋅F′(xi)G(x)\sum_{i1}^{\infin}x^i\cdot F(x^i)G(x)i1∑∞xi⋅F′(xi)
Gn∑i1∞[xn−i]F′(xi)G_n\sum_{i1}^{\infin}[x^{n-i}]F(x^i)Gni1∑∞[xn−i]F′(xi)
经过大胆的观察和仔细的猜想
Gn∑d∣n(n−dd1)Fn−dd1G_n\sum_{d\mid n}(\frac {n-d}d1)F_{\frac {n-d}d1}Gnd∣n∑(dn−d1)Fdn−d1
Gn∑d∣n(nd)FndG_n\sum_{d\mid n}(\frac nd)F_{\frac nd}Gnd∣n∑(dn)Fdn
Gn∑d∣ndFdG_n\sum_{d\mid n}d F_dGnd∣n∑dFd
然后每求出一个FFF就可以调和级数复杂度求出之前的GGG就可以分治 NTT 了。
但是分治时如果L1L1L1GGG可能不够用。解决办法是先不计算不够的地方的贡献在后面再把它加上。
具体的讲如果我们要计算F1∼midF_{1\sim mid}F1∼mid对Fmid1∼RF_{mid1\sim R}Fmid1∼R的贡献我们只计算iii不超过midmidmid的GiG_iGi的贡献这样少算了Gmid1,R−1G_{mid1,R-1}Gmid1,R−1的贡献。而这部分贡献可以通过RRR之前交换FFF和GGG做一次类似的卷积计算出来。详见代码。
复杂度O(nlog2n)O(n\log ^2n)O(nlog2n)
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 524288
using namespace std;
const int MOD998244353;
typedef long long ll;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD;p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
int rt[2][24],r[MAXN],l,lim;
inline void init(){lim1l;for (int i0;ilim;i) r[i](r[i1]1)|((i1)(l-1));}
inline void NTT(int* a,int type)
{for (int i0;ilim;i) if (ir[i]) swap(a[i],a[r[i]]);for (int L0;Ll;L){int mid1L,lenmid1;ll Wnrt[type][L1];for (int s0;slim;slen)for (int k0,w1;kmid;k,ww*Wn%MOD){int xa[sk],y(ll)w*a[smidk]%MOD;a[sk]add(x,y),a[smidk]dec(x,y);}}if (type){int tinv(lim);for (int i0;ilim;i) a[i](ll)a[i]*t%MOD;}
}
int f[MAXN],g[MAXN],n;
int a[MAXN],b[MAXN];
void solve(int L,int R)
{if (LR){if (L1) f[L](ll)f[L]*inv(L-1)%MOD;int t(ll)L*f[L]%MOD;for (int iL;in;iL) g[i]add(g[i],t);return;}int mid(LR)1;solve(L,mid);int lenR-L;for (l0;(1l)(len1);l);init();if (L1){for (int i0;ilim;i) a[i]b[i]0;for (int iL;imid;i) a[i]f[i],b[i]g[i];NTT(a,0);NTT(b,0);for (int i0;ilim;i) a[i](ll)a[i]*b[i]%MOD;NTT(a,1);for (int imid1;iR;i) f[i]add(f[i],a[i]);}else{for (int i0;ilim;i) a[i]b[i]0;for (int iL;imid;i) a[i-L]f[i];for (int i0;ilen;i) b[i]g[i];NTT(a,0);NTT(b,0);for (int i0;ilim;i) a[i](ll)a[i]*b[i]%MOD;NTT(a,1);for (int imid1;iR;i) f[i]add(f[i],a[i-L]);for (int i0;ilim;i) a[i]b[i]0;for (int iL;imid;i) a[i-L]g[i];for (int i0;ilen;i) b[i]f[i];NTT(a,0);NTT(b,0);for (int i0;ilim;i) a[i](ll)a[i]*b[i]%MOD;NTT(a,1);for (int imid1;iR;i) f[i]add(f[i],a[i-L]);}solve(mid1,R);
}
int main()
{rt[0][23]qpow(3,119),rt[1][23]inv(rt[0][23]);for (int i22;i0;i--){rt[0][i](ll)rt[0][i1]*rt[0][i1]%MOD;rt[1][i](ll)rt[1][i1]*rt[1][i1]%MOD;}scanf(%d,n);f[1]1;solve(1,n);int ansf[n];printf(%d\n,ans);return 0;
}
