听舍友讲的,但是一个舍友多除了几次 222,一个舍友忘取模了。
显然每个连通块内可以两两交换,所以它内所有点都可以任意排列。
记 coloru,i\text{color}_{u,i}coloru,i 为第 uuu 个连通块内字符为 iii 的数量。
如果能交换任意次,答案为 ∏(∑coloru,i)!∏(coloru,i!)\prod \frac{(\sum \text{color}_{u,i})!}{\prod (\text{color}_{u,i}!)}∏∏(coloru,i !)(∑coloru,i )! 。
然后注意到如果字符两两不同,交换奇数次与交换偶数次的情况数相同(刚刚那个好像是假的);1010010^{100}10100 为偶数。
证明:
1. 不会证。
2. 注意到 10100=2×(5×1099)10^{100}=2\times (5\times 10^{99})10100=2×(5×1099),5×10995\times 10^{99}5×1099 为正整数。
所以如果所有连通块内字符两两不同,那最终所有情况等价于只交换偶数次,此时答案要除以 222;否则交换一次相同的字符就能取到交换奇数次了。
做完了。