【AGC005F】Many Easy Problems

考虑一个点\(i\)对\(k\)的贡献

考虑用所有方案减去不包含\(i\)的方案,就是

\(\binom{n}{k}-\sum\binom{s_i}{k}\),其中\(s\)为删除\(i\)后各个连通块的大小。

我们可以对同一个\(k\)一起计算,那么假设我们得到\(\binom{i}{k}\)的系数为\(a_i\)

\(k\)的答案就是\(\sum_{i=k}^{n}a_i\binom{i}{k}=\frac{1}{k!}\sum_{i=k}^{n}\frac{a_i i!}{(i-k)!}\)

对于每个\(k\),\(a_i\)是相同的,那么只要做一次FFT即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz