题解看吐了来问一下。

昨天的 ABC 的 G 经过一些转化之后可以变成如下问题：

一个长度为 $n$ 的环，只保留若干条边，一种方案的权值是剩下的所有连通块的大小之积，问所有保留 $k$ 条边的方案的权值之和。

我在翻 AC 的提交记录的时候发现，如果设答案是 $f(n,k)$ ，那么 $f(n,k) = \binom{2*n-k}{k}+\binom{2*n-k-1}{k-1}$。

证了很久完全不会，求某位大佬来教教我。

AT 官方题解：“因为是这么一个问题，so it can be expressed as the sum a binomial coefficients。”

禁止无意义回复。