做化妆品网站的意义,中山外贸网站建设报价,凡科建站的优势,网站专栏的作用树的计数 II
题目链接#xff1a;YBT2023寒假Day12 C
题目大意
给你一个长度为 n 的排列 p#xff0c;问你有多少个不同的有标号无根树#xff0c;满足如果 i,j 有边那 pi,pj 也有边。
思路
首先可以把排列变成置换环。 注意到是树#xff0c;发现一个置换中似乎不太可…树的计数 II
题目链接YBT2023寒假Day12 C
题目大意
给你一个长度为 n 的排列 p问你有多少个不同的有标号无根树满足如果 i,j 有边那 pi,pj 也有边。
思路
首先可以把排列变成置换环。 注意到是树发现一个置换中似乎不太可能内部连边因为很可能会出现环但显然是有情况可以的。 考虑讨论 首先大小 111 不需要也就是可以大小为 222 可以。 然后发现一个环你表示成 a1,a2,...,aka_1,a_2,...,a_ka1,a2,...,ak会发现你连 a1,axa_1,a_xa1,ax 至少长度大于 222 都不行。 如果 x≠k/21x\neq k/21xk/21那往后推进就变成了 ax,a2x−1a_x,a_{2x-1}ax,a2x−1再由不等式有着肯定不是 a1a_1a1那就跳到了一个新的点那每次都会跳到一个跟之前不一样的点而且不会停下来那一定就是成了环而且点的个数大于 222所以肯定不是树。 然后如果 xk/21xk/21xk/21会发现变成了 k/2k/2k/2 个连通块它们内部无法合并如果要跟外部连就会每个连通块都连出去两条边一定会变成环所以也不行。
那简单总结一下就是内部连边只有 k1/2k1/2k1/2 的时候才行。 然后你似乎要考虑一个环是选内部连边还是外部连边。 但是当你内部连边多个的时候你会发现好像不能把它们连起来。 不过准确来说 111 不许要内部连边所以 111 可以外部连但是你 222 似乎不能和另一个 222 内部连边在弄到一起222 也不能内部连边之后跟 111 连到一起。
也就是说又有了一个结论 至多只能选一个大小为 222 的环内部连边而当有大小为 111 的环存在时不会有内部连边。 接下来考虑外部连边考虑两个环大小为 x,yx,yx,y 能不能连。 思考一下会发现当我们设 x⩽yx\leqslant yx⩽y 的时候条件是 x∣yx|yx∣y。 那当 x∣yx|yx∣y 的时候显然是可以连边形成 xxx 个连通块的。 那我们考虑证明 x∤yx\nmid yx∤y 的时候会出现环 那如果有边 (a0,b0)(a_0,b_0)(a0,b0)就会有 (a0,bx),(aymodx,b0),(aymodx,bx)(a_0,b_x),(a_{y\bmod x},b_0),(a_{y\bmod x},b_x)(a0,bx),(aymodx,b0),(aymodx,bx)。 那这四条边就成环了。 所以能连边的条件就是 x∣yx|yx∣y。 那因为有编号所以还有连边方式显然连了一个之后后面都确定那你就可以让一开始那个点最后在哪个连通块所以是 xxx 个方案。 考虑怎么拼起来 会发现如果 xyxyxy 的时候x,yx,yx,y 之间的连边可以说是单向的。 但是 xyxyxy 的时候也可以连边但是这个是双向的。 那你考虑处理 xyxyxy 的具体而言就是当有 nxn_xnx 个大小为 xxx 的我们先算出把它组合成无根树森林的情况再补上它们接到之前的树上的方案。 那组合成无根树森林我们可以用 prufer 来搞弄一个 000 号虚拟点
但是你会发现接入到原来树中每个位置是取决于你接入的位置的。 考虑把 prufer 变形考虑 prufer 序列怎么来的 每次找到编号最大 / 最小的叶子记录连着它的点把这个叶子删去直到剩下两个点。 那记录连着它的点这个时候我们就要乘上这个点代表的大小。 那就原本是贡献 111现在是贡献 xxx那我们可以把每个可以贡献的位置 xxx让它贡献 cntx∗xcnt_x*xcntx∗x 而不是 cntxcnt_xcntx。 那在这里就全是 cntx∗xcnt_x*xcntx∗x。 然后至于 000 号虚拟点那你可以理解为连向它就是连向之前树中可以连的任意一个那任意一个都会产生各自的贡献那你就把每个可以的位置的 cntx∗xcnt_x*xcntx∗x 加起来即可记为 sumsumsum。
不过我们 000 号点是虚拟的那我们每次选编号大的最后就可以剩下 000 号点。 不过有一个特别特殊的地方是你最后的两条边之间的方案也要记得乘上那在这里就是 sumsumsum因为这两个点其中一个一定是 000 然后按着做的就完事了。
代码
#includecstdio
#define ll long long
#define mo 998244353using namespace std;const int N 5e5 1000;
int n, a[N], sz[N], tot;
bool in[N];int dfs(int now) {if (in[now]) return 0;in[now] 1; return 1 dfs(a[now]);
}ll ksm(ll x, ll y) {ll re 1; x % mo;while (y) {if (y 1) re re * x % mo;x x * x % mo; y 1;}return re;
}ll Prufer(int n) {if (n 1) return 1;return ksm(n, n - 2);
}void slove() {scanf(%d, n);for (int i 1; i n; i) scanf(%d, a[i]);for (int i 1; i n; i) {if (in[i]) continue;sz[dfs(i)];}ll ans 0, cnt 0;if (sz[1]) {ans Prufer(sz[1]);cnt sz[1];if (sz[2]) {ll num cnt;(ans * num * ksm(2 * sz[2] num, sz[2] 1 - 2) % mo) % mo;cnt sz[2];}}else if (sz[2]) {if (sz[2] 1) ans 1;else ans 2 * ksm(2 * sz[2], sz[2] - 2) * sz[2] % mo;cnt sz[2];}for (int i 3; i n; i) {if (!sz[i]) continue;ll num 0;for (int j 1; j * j i; j) if (i % j 0) {(num 1ll * j * sz[j] % mo) % mo;//接口*接这个接口的方案if (i / j ! j i / j ! i) (num 1ll * (i / j) * sz[i / j] % mo) % mo;}(ans * num * ksm(i * sz[i] num, sz[i] 1 - 2) % mo) % mo;cnt sz[i];}printf(%lld\n, ans);for (int i 1; i n; i) in[i] 0, sz[i] 0;tot 0;
}int main() {freopen(count.in, r, stdin);freopen(count.out, w, stdout);int T; scanf(%d, T);while (T--) slove();return 0;
}
