基环树和点度数相关的计数：CF1863G

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132696642

https://codeforces.com/contest/1863/problem/G

首先建图，然后分析出交换在图上的变化，发现每条点最多只有一个入边标粗，求最终形态。

首先可以猜答案为 $\prod_{v}(\mathrm{in}_v + 1)$ ，但是环上会有不合法的和重复的。

发现以下情况会重复：

总共有 $\sum_{i=1}^k\mathrm{in}_{c_i}$ 种，重复有 $\sum_{i=1}^k\mathrm{in}_{c_i}-1$ 种，加上之前不合法的有 $\sum_{i=1}^k\mathrm{in}_{c_i}$ 种，所以总方案为：

$$\prod_{\text{cycles}}\left(\prod_{i=1}^k(\mathrm{in}_{c_i} + 1) - \sum_{i=1}^k\mathrm{in}_{c_i}\right)\cdot\prod_{\text{other }v}(\mathrm{in}_v + 1).$$