D. 【GENOIP#41】取啊
1 s
512 MB
题目描述
小可可又在造数据，只不过这次是一个联通图。
小可可要造一个 $n$ 个点的联通图，由于她非常懒，于是决定每次在 $[1, n]$ 中独立地等概率随机两个点 $u, v$ （可以相同），然后将 $u, v$ 之间连一条边。
小可可发现要等到整张图联通需要不少时间，于是问你期望连多少次边后整张图联通，答案对一个质数 $p$ 取模。
输入格式
小可可又在造数据，只不过这次是一个联通图。
小可可要造一个 $n$ 个点的联通图，由于她非常懒，于是决定每次在 $[1, n]$ 中独立地等概率随机两个点 $u, v$ （可以相同），然后将 $u, v$ 之间连一条边。
小可可发现要等到整张图联通需要不少时间，于是问你期望连多少次边后整张图联通，答案对一个质数 $p$ 取模。
输出格式
输出一个整数，表示期望连边次数对 $p$ 取模的结果。
样例 1
样例 2
样例 3
样例 4
样例 5
数据范围与提示
数据规模与约定
对于 $20 \%$ 的数据， $n \le 5$ ；
对于 $40 \%$ 的数据， $n \le 20$ ；
对于 $60 \%$ 的数据， $n \le 50$ ；
对于 $100 \%$ 的数据， $1 \le n \le 100, 10^8 \le p \le 10^9 + 9$ 。
OI
Contest Ended