## [题目链接](https://qoj.ac/contest/2607/problem/15039) 赛时因为关闭流同步后 `cout` 和 `printf` 混用导致浪费超多时间找错误没时间思考这道题（但有时间也做不出来） （现在开始完全使用 `cin&cout` 了，这是第一份代码） 这是一个超级抽象的 DP 题！！！ （题解中有一部分把每个点的单独贡献拎出来，每个点的贡献构成的可重集作为标签，两棵树的 Hash 相同当且仅当标签相同，然后转化成 DP，比较巧妙但其实构建 DP 不一定要想到这个） 考虑先构造一个不充分的 DP：令 $f_i$ 表示 $i$ 个节点的树 Hash 不同的个数，$f_n$ 为答案 计算 $f_i$，令左右儿子的大小分别为 $l,r$，满足 $l+r=i-1$ 显然左右子树交换后 Hash 不变，所以不妨 $l<r$ 容易发现当 $l$ 不同的两种构造通过改变映射函数一定可以让他们的 Hash 不同，并且 $f_l$ 和 $f_r$ 通过乘法原理构造的不同情况间一定也可以让他们的 Hash 不同 很容易得到递推式 $f_i=\sum f_lf_r$ 但还漏了一种 $l=r$ 的情况，这时乘法原理显然不适用，比如题解中给出的情况：  （S1 和 S2 是两个大小相同但 Hash 不同的树） 这时我们不得不单独计算出对于大小为 $(i-1)/2$ 的两棵树的 Hash 和能有多少不同的值 这时就很不妙，因为这个也没办法单独求解 可以把状态扩充，$f_{i,j}$ 表示选取 $j$ 个大小为 $i$ 的树，它们的 Hash 和能有多少不同的值，答案是 $f_{n,1}$，刚刚要求的就是 $f_{\frac{i-1}{2},2}$。 对于计算 $f_{i,j}$ 还是按照之前的做法 有 $j$ 棵树，每棵树都有一个左儿子大小 $l$，很容易看出两种方案中如果存在一个左儿子大小 $l$，使得第一种方案中左儿子大小为 $l$ 的树的个数和第二种方案不同，就一定可以构造映射函数使得他们的 Hash 和不同！ 就相当于做一个背包，这 $j$ 棵树中有多少棵树的左儿子大小为 $l$ 假设其中有 $k$ 棵树的左右儿子大小分别为 $l,r$ （因为映射函数的任意性，以下情况保证 Hash 不同比较好想象） 当 $l\ne r$ 时，$f_{i,j}\leftarrow f_{i,j-k}\cdot f_{l,k}\cdot f_{r,k}$ 当 $l=r$ 时，$f_{i,j}\leftarrow f_{i,j-k}\cdot f_{l,2k}$ （这其实就是一个卷积的形式） 然后这虽然有四重循环，但时间复杂度很好证明时 $O(n^2\log n)$ ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; const int N=3e3+10; int n, p, c[N], f[N][N*2], g[N]; void mul(int *a, int *b, int n) { fill(c, c+n+1, 0); for (int i=0; i<=n; i++) for (int j=0; j<=n-i; j++) c[i+j]=(c[i+j]+a[i]*b[j])%p; copy(c+1, c+n+1, a+1); } void solve() { cin>>n>>p; fill(f[0], f[0]+n*2+1, 1); for (int i=1; i<=n; i++) { fill(f[i]+1, f[i]+n+1, 0); f[i][0]=1; for (int l=0; l<=(i-1)/2; l++) { int r=i-1-l; for (int k=0; k<=n/i; k++) if (l==r) g[k]=f[l][k*2]; else g[k]=f[l][k]*f[r][k]%p; mul(f[i], g, n/i); } } cout<<f[n][1]<<endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T=1; cin>>T; while (T--) solve(); return 0; } ``` Loading... ## [题目链接](https://qoj.ac/contest/2607/problem/15039) 赛时因为关闭流同步后 `cout` 和 `printf` 混用导致浪费超多时间找错误没时间思考这道题（但有时间也做不出来） （现在开始完全使用 `cin&cout` 了，这是第一份代码） 这是一个超级抽象的 DP 题！！！ （题解中有一部分把每个点的单独贡献拎出来，每个点的贡献构成的可重集作为标签，两棵树的 Hash 相同当且仅当标签相同，然后转化成 DP，比较巧妙但其实构建 DP 不一定要想到这个） 考虑先构造一个不充分的 DP：令 $f_i$ 表示 $i$ 个节点的树 Hash 不同的个数，$f_n$ 为答案 计算 $f_i$，令左右儿子的大小分别为 $l,r$，满足 $l+r=i-1$ 显然左右子树交换后 Hash 不变，所以不妨 $l<r$ 容易发现当 $l$ 不同的两种构造通过改变映射函数一定可以让他们的 Hash 不同，并且 $f_l$ 和 $f_r$ 通过乘法原理构造的不同情况间一定也可以让他们的 Hash 不同 很容易得到递推式 $f_i=\sum f_lf_r$ 但还漏了一种 $l=r$ 的情况，这时乘法原理显然不适用，比如题解中给出的情况：  （S1 和 S2 是两个大小相同但 Hash 不同的树） 这时我们不得不单独计算出对于大小为 $(i-1)/2$ 的两棵树的 Hash 和能有多少不同的值 这时就很不妙，因为这个也没办法单独求解 可以把状态扩充，$f_{i,j}$ 表示选取 $j$ 个大小为 $i$ 的树，它们的 Hash 和能有多少不同的值，答案是 $f_{n,1}$，刚刚要求的就是 $f_{\frac{i-1}{2},2}$。 对于计算 $f_{i,j}$ 还是按照之前的做法 有 $j$ 棵树，每棵树都有一个左儿子大小 $l$，很容易看出两种方案中如果存在一个左儿子大小 $l$，使得第一种方案中左儿子大小为 $l$ 的树的个数和第二种方案不同，就一定可以构造映射函数使得他们的 Hash 和不同！ 就相当于做一个背包，这 $j$ 棵树中有多少棵树的左儿子大小为 $l$ 假设其中有 $k$ 棵树的左右儿子大小分别为 $l,r$ （因为映射函数的任意性，以下情况保证 Hash 不同比较好想象） 当 $l\ne r$ 时，$f_{i,j}\leftarrow f_{i,j-k}\cdot f_{l,k}\cdot f_{r,k}$ 当 $l=r$ 时，$f_{i,j}\leftarrow f_{i,j-k}\cdot f_{l,2k}$ （这其实就是一个卷积的形式） 然后这虽然有四重循环，但时间复杂度很好证明时 $O(n^2\log n)$ ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; const int N=3e3+10; int n, p, c[N], f[N][N*2], g[N]; void mul(int *a, int *b, int n) { fill(c, c+n+1, 0); for (int i=0; i<=n; i++) for (int j=0; j<=n-i; j++) c[i+j]=(c[i+j]+a[i]*b[j])%p; copy(c+1, c+n+1, a+1); } void solve() { cin>>n>>p; fill(f[0], f[0]+n*2+1, 1); for (int i=1; i<=n; i++) { fill(f[i]+1, f[i]+n+1, 0); f[i][0]=1; for (int l=0; l<=(i-1)/2; l++) { int r=i-1-l; for (int k=0; k<=n/i; k++) if (l==r) g[k]=f[l][k*2]; else g[k]=f[l][k]*f[r][k]%p; mul(f[i], g, n/i); } } cout<<f[n][1]<<endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T=1; cin>>T; while (T--) solve(); return 0; } ``` 最后修改：2026 年 01 月 04 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏