传送门：点击打开链接
题意：n个点，每个点至少被一条边覆盖，不存在自环和重边。问有多少种情况
一个非常有意思的递推，其实可以利用容斥的思想去考虑这道题目
设F[n]表示为n个点的情况数，那么最多会存在n*(n-1)/2条边，这些边中，每条边都是可有可无。如果不考虑不满足条件的情况（也就是有的点没有被边覆盖的情况），可能的情况数为pow(2,n*(n-1)/2)，也就是考虑每一条边是否存在
那么对于答案而言，不能有点没有被覆盖，接下来我们就来枚举点被边覆盖的个数，设为k
当有k个点被覆盖了，这k个点的情况数就是F[k],那么这k个点分别是哪k个，需要组合数C(n,k)，所以对于k个点被覆盖时，不满足条件的总类数就是F[k]*C(n,k)
k可以从1枚举到n-1，然后还要考虑一个特殊情况，就是没有一个点被边覆盖，这只有1种情况。
综上所述，答案是F[n]=pow(2,n*(n-1)/2)-segma(F[k]*C(n,k))其中1<=k<=n-1
import java.util.Scanner;
import java.math.*;public class Main {static final int MX = 100 + 5;public static void main(String[] args) {Scanner cin = new Scanner(System.in);BigInteger zero = BigInteger.valueOf(0);BigInteger one = BigInteger.valueOf(1);BigInteger two = BigInteger.valueOf(2);BigInteger[][] C = new BigInteger[MX][MX];C[0][0] = one;for (int i = 1; i < MX; i++) {C[i][0] = C[i][i] = one;for (int j = 1; j < i; j++) {C[i][j] = C[i - 1][j - 1].add(C[i - 1][j]);}}BigInteger f[] = new BigInteger[MX];f[1] = one;f[2] = one;for (int i = 3; i < MX; i++) {f[i] = two.pow(i * (i - 1) / 2).subtract(one);for (int k = 2; k <= i - 1; k++) {f[i] = f[i].subtract(C[i][k].multiply(f[k]));}}while (cin.hasNext()) {int n = cin.nextInt();System.out.println(f[n]);}}
}