题意:输入n,m(n,m<500),问有n的点且联通块为m个的图有多少

题解:

dp[i][j]代表取前i个形成j个联通块的个数

第i个单独考虑,可以枚举联通块的大小K:[1, i-j+1]

要保证枚举的时候方案不会重复,那么不能写作c(i, k)

这样dp[i1][j]和dp[i2][j]会有重复的部分

所以这里固定下来第i个是必须要取的

那么方案数就是c(i-1, k-1)

所以可以得到递推式

for(int k=1;k<=i-j+1;k++)

dp[i][j] += c(i-1, k-1)*dp[i-k][j-1]*dp[k][1];

dp[k][1]要单独计算,它的意义是k个数形成一个联通块的方案数:

dp[k][1] = 2^(k*(k-1)/2);

for(int i=2;i<=k;i++) dp[k][1] -= dp[k][i];

注意题目要求至少一条边,所以当m==1时,答案要减1

要预处理

#include 
     
      #define ll long long#define maxn 510using namespace std;const ll mod = 998244353;ll c[maxn][maxn], n, m, dp[maxn][maxn];void init(){    for(ll i=0;i<=500;i++){        c[i][0] = c[i][i] = 1;        for(ll j=1;j
      
       >= 1;    }    return ans;}int main(){    init();    scanf("%lld%lld", &n, &m);    for(ll i=1;i<=n;i++){        for(ll j=2;j<=i;j++)            for(ll k=1;k<=i-j+1;k++)                dp[i][j] = (dp[i][j]+c[i-1][k-1]*dp[i-k][j-1]%mod*dp[k][1]%mod)%mod;        dp[i][1] = f(2, (i*(i-1)/2));        for(ll j=2;j<=i;j++)            dp[i][1] = (dp[i][1]+mod-dp[i][j])%mod;    }    if(m == 1) printf("%lld\n", dp[n][1]-1);    else printf("%lld\n", dp[n][m]);    return 0;}