「ZJOI2018」树

本文主要是介绍「ZJOI2018」树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

设大小为 $n$ 的不同的树为 $T_{n,1},\dots ,T_{n,m}$
其中每个 $T$ 表示这类树的一个集合
那么求的就是 $\frac{1}{(n-1){!}^k}{\sum }_i|T_{n,i}{|}^k$

参考：传送门

• 设 置换 $f$ 下的不动点为 $fix(f)$
  所有 $f$ 使得状态 $X$ 在该置换下为不动点的集合为 $SG(X)$
• 我们设 $F_n={\sum }_i|T_{n,i}{|}^k$
  考虑将根去掉，形成若干子树，我们按大小从大到小枚举每棵子树
  设 $G_{n,m}$ 表示除根以外每个子树都 $\le m$ 的 $\sum |T_{n,i}{|}^k$
  我们枚举最大值个数为 $c$
  那么即 $G_{n,m}={\sum }_{c=0}^{\lfloor \frac{n-1}{m}\rfloor }{\left(\genfrac{}{}{0ex}{}{n-1}{c\times m}\right)}^k{G}_{n-c\times m,m-1}\times H_{m,c}$
  其中 $H_{m,c}$ 表示 $c$ 个大小为 $m$ 的子树的 $\sum |{\mathcal{T}}_i{|}^k$
  （这里姑且用 ${\mathcal{T}}_i$ 表示每种不同的森林）
  考虑计算 $H_{m,c}$，首先是分配标号的方案数
  我们设大小为 $m$ 的子树编号分别为 $1,2,\dots ,t$
  注意编号相同的若干个子树分配标号是算重了的
  我们设选了 $p$ 种子树，每个树选了 $b_i$ 次，那么方案数就是 $(\frac{(cm)!}{m{!}^c}\times \prod \frac{1}{b_i!}{)}^k{w}_X$
  其中 $X$ 表示选的树标号的可重无序集合
  $w_X$ 表示这个集合中，每棵树的标号都是 $[1,m]$，每种不同的森林的大小的 $k$ 次方之和
• 现在考虑计算 $w_X$
  一个直观的想法是这样计算：${\prod }_{i=1}^p({\sum }_{j=1}^t|T_j{|}^{a_{i}k})$
  这个算的是啥呢 /yun：点了若干个集合（每个集合大小为 $a_i$，集合内相同，集合间无限制）
  注意到，对于一个置换 $f$，若满足有 $p$ 个环，每个环大小为 $b_i$，那么
  ${\sum }_{X\in fix(f)}{w}_X={\prod }_{i=1}^p({\sum }_{j=1}^t|T_j{|}^{a_{i}k})$
  （注意这里需要把 $X$ 修成有序的可重集合，这样才能在每个置换下枚举到）
  这里我们需要在状态中设计一个系数 $j$ 表示 $k\leftarrow k\times j$
  那么 ${\sum }_{X\in fix(f)}{w}_X={\prod }_{i=1}^p{F}_{m,b_i}$，我们要算的就是 $(\frac{(cm)!}{m{!}^c}\times \prod \frac{1}{b_i!}{)}^k\frac{\prod b_i!w_X}{c!}$
  考虑分配系数 $A$ ，算出 ${\sum }_X{w}_X{\sum }_{f\in SG(X)}{A}_f$ 使得其等于 $(\frac{(cm)!}{m{!}^c}\times \prod \frac{1}{b_i!}{)}^k\frac{\prod b_i!w_X}{c!}$
  即 ${\sum }_{f\in SG(X)}{A}_f=(\frac{(cm)!}{m{!}^c}\times \prod \frac{1}{b_i!}{)}^k\frac{\prod b_i!}{c!}$
  根据题解观察和经验
  我们考虑将 $A$ 写成 ${\prod }_i{B}_{b_i}$，即每个环长大小系数之积
  注意到 $SG(X)$ 中的 $f$ 中的环一定是 $X$ 中的分解，设 $B(x)={\sum }_{i\ge 1}\frac{x^i{B}_i}{i}$
  那么 ${\prod }_{i=1}^p[x^{b_i}]\exp (B)=(\frac{(cm)!}{m{!}^c}\times \prod \frac{1}{b_i!}{)}^k\frac{1}{c!}$，其中 $(\frac{(cm)!}{m{!}^c}{)}^k\frac{1}{c!}$ 为常数
  于是我们构造 $[x^i]\exp B=\frac{1}{i{!}^k}$ 就可以了
  那么现在只需要算出 ${\sum }_f{A}_f{\prod }_{i=1}^p{F}_{m,b_i}$，直接枚举环：$\exp ({\sum }_{i\ge 1}\frac{B_i{F}_{m,i}{x}^i}{i})$
• 最后的式子就长这样：
  $G_{n,m,j}={\sum }_c{G}_{n-mc,m-1,j}\times [x^c]\exp ({\sum }_{i\ge 1}\frac{B_i{G}_{m,m-1,j}{x}^i}{i})$
  其中 $n\times j\le N$，对于每个 $n$，需要 $n\log n$ 的时间来转移
  所以这里的复杂度为 $\mathcal{O}({\sum }_{n=1}^N\frac{N}{n}n\log n=N^2\log N)$（注意避免转移时的快速幂）
  然后考虑计算 $B$ 的时间：$\mathcal{O}({\sum }_{n=1}^N{\sum }_{m=1}^N(\frac{N}{nm}{)}^2=N^2)$
• 个人觉得中间算两次的部分特别巧妙
  即 ${\sum }_{X\in fix(f)}{w}_X={\prod }_{i=1}^p{F}_{m,b_i}$，然后转成枚举置换

#include<bits/stdc++.h>
#define cs const
#define pb push_backusing namespace std;
typedef vector<int> vi;int Mod;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a, b); }
void Dec(int &a, int b){ a = dec(a, b); }
void Mul(int &a, int b){ a = mul(a, b); }
int ksm(int a, int b){int ans = 1; for(; b; b >>= 1, Mul(a, a))if(b & 1) Mul(ans, a); return ans;
}cs int N = 2e3 + 50; 
int n, k, dp[N][N];
int B[N], fc[N], ifc[N], iv[N];
int p[N][N], ip[N][N];
void ln(int *a, int n){static int b[N]; b[0] = 0; for(int i = 1; i <= n; i++){b[i] = mul(i, a[i]);for(int j = 1; j < i; j++)Dec(b[i], mul(b[j], a[i - j]));} for(int i = 0; i <= n; i++)a[i] = mul(b[i], iv[i]);
}
void Exp(int *a, int n){static int b[N];for(int i = 0; i <= n; i++)b[i] = 0, Mul(a[i], i);b[0] = 1; for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++)Add(b[i], mul(a[j], b[i - j]));Mul(b[i], iv[i]);}for(int i = 0; i <= n; i++) a[i] = b[i];
}
void work(int m, int j, int n){for(int i = 0; i <= n; i++)B[i] = ksm(ifc[i], 1ll * k * j % (Mod - 1));ln(B, n); for(int i = 1; i <= n; i++)Mul(B[i], dp[j * i][m]); Exp(B, n);
}
int main(){#ifdef FSYofreopen("1.in", "r", stdin);#endifcin >> n >> k >> Mod;fc[0] = ifc[0] = 1; for(int i = 1; i <= n; i++)	fc[i] = mul(fc[i - 1], i);ifc[n] = ksm(fc[n], Mod - 2);for(int i = n - 1; i; i--)ifc[i] = mul(ifc[i + 1], i + 1);iv[1] = 1; for(int i = 2; i <= n; i++)iv[i] = mul(Mod - Mod / i, iv[Mod % i]);for(int i = 1; i <= n; i++)dp[i][1] = 1; for(int i = 1; i <= n; i++) {int mt = ksm(i, k), imt = ksm(iv[i], k);p[i][1] = mt, ip[i][1] = imt;for(int j = 2; j <= n / i; j++)p[i][j] = mul(p[i][j - 1], mt),ip[i][j] = mul(ip[i][j - 1], imt);}for(int i = 1; i < n; i++) for(int j = 1; j <= n / i; j++){ work(i, j, n / (i * j));static int pw[N], ipw[N];for(int l = 1; l <= n / j; l++)pw[l] = p[l][j], ipw[l] = ip[l][j];for(int l = n / j; l > i; l--)for(int c = 1; c * i <= l; c++){int w = mul(B[c], dp[j][l - c * i]);Mul(w, mul(ipw[l], pw[l - c * i]));Add(dp[j][l], w);}} cout << mul(ksm(n, k), dp[1][n]);return 0; 
}

这篇关于「ZJOI2018」树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---