题目链接
d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示当前到第i个点用了j个边最大联通块是否为L的方案数。 满足题目的联通快必然是一个链树或者一个环。分树和环来进行转移即可。 注意这里大小为n的环有 ( n − 1 ) ! / 2 (n-1)!/2 (n−1)!/2种，大小为n的一条链树有 n ! / 2 n!/2 n!/2种。 注意一下特殊的case，例如大小为1 2的时候。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int n,m,l; const int mod=1e9+7; const int inv2=(mod+1)/2; int add(int x,int y){ x+=y; if(x>=mod)x-=mod; return x; } int mul(int x,int y){ return 1ll*x*y%mod; } int ksm(int x,int y){ int z=1; while(y){ if(y&1)z=1ll*z*x%mod; x=1ll*x*x%mod; y>>=1; } return z; } int fac[N],inv[N]; void P(){ fac[0]=1; for(int i=1;i<=300;i++)fac[i]=mul(fac[i-1],i); inv[300]=ksm(fac[300],mod-2); for(int i=299;i>=0;i--)inv[i]=mul(inv[i+1],i+1); } int C(int x,int y){ if(x<y)return 0; return mul(fac[x],mul(inv[y],inv[x-y])); } int dp[333][333][2]; int main() { ios::sync_with_stdio(false); cin>>n>>m>>l;P(); dp[0][0][0]=1; for(int i=1;i<=n;i++){ for(int j=i-1;j>=0&&i-j<=l;j--){ int now=i-j; for(int k=m;k>=now-1&&k>=0;k--){ for(int sta=0;sta<2;sta++) { int res=(sta|(now==l)); if (k - now >= 0&&now>1){//cycle if(now>2)dp[i][k][res] = add(dp[i][k][res], mul(dp[j][k - now][sta], mul(C(n - j-1, now-1),mul(fac[now-1],inv2)))); else dp[i][k][res] = add(dp[i][k][res], mul(dp[j][k - now][sta], mul(C(n - j-1, now-1),1))); } if(now>1)dp[i][k][res] = add(dp[i][k][res], mul(dp[j][k - now + 1][sta], mul(C(n - j-1, now-1),mul(fac[now],inv2)))); else dp[i][k][res] = add(dp[i][k][res], mul(dp[j][k - now + 1][sta], mul(C(n - j-1, now-1),1))); } } } } cout<<dp[n][m][1]<<'\n'; return 0; }