[ABC180F] Unbranched
题面翻译
求 \(N\) 个点，\(M\) 条边且满足以下条件的图的数量：
-
图中无自环；
-
每个点度数最多为 \(2\)；
-
连通块大小的最大值恰好为 \(L\)。
答案对 \(10^9+7\) 取模。
\(2\le N\le300\)，\(1\le M,L\le N\)。
题目描述
頂点にラベルが付き辺にはラベルが付いていない $ N $ 頂点 $ M $ 辺の単純とも連結とも限らないグラフであって、以下の条件を満たすものの個数を $ 10^9+7 $ で割ったあまりを求めてください。
- 自己ループを持たない
- すべての頂点の次数が $ 2 $ 以下である
- 各連結成分のサイズを並べたとき、その最大値がちょうど $ L $ である
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ M $ $ L $
输出格式
答えを出力せよ。
样例 #1
样例输入 #1
3 2 3
样例输出 #1
3
样例 #2
样例输入 #2
4 3 2
样例输出 #2
6
样例 #3
样例输入 #3
300 290 140
样例输出 #3
211917445
提示
制約
- $ 2\ \leq\ N\ \leq\ 300 $
- $ 1\leq\ M\ \leq\ N $
- $ 1\ \leq\ L\ \leq\ N $
- 入力はすべて整数
Sample Explanation 1
頂点に $ 1 $ から $ N $ の番号を付けたとき、以下の $ 3 $ 通りのグラフが条件を満たします。 - $ 1-2 $ 間と $ 2-3 $ 間に辺がある。 - $ 1-2 $ 間と $ 1-3 $ 間に辺がある。 - $ 1-3 $ 間と $ 2-3 $ 間に辺がある。
解题思路
看到计数题我们就可以用 \(DP\) 来解决。
钦定最大为 \(L\) 很麻烦，我们可以设计函数 \(ans(n,m,l)\) 表示满足题目要求的 \(n\) 点 \(m\) 边，最大连通块节点个数不超过 \(l\) 的图的个数，那么答案就为 \(ans(n,m,l)-ans(n,m,l-1)\) 。
对于每次求解 \(ans(n,m,l)\) ，就采取 \(DP\) 的方式。
根据题目要求，一个连通块只有两种可能形式，圆与链，设点数为 \(x\) ，边数分别为 \(x\) 与 \(x-1\)。
每种链有 \(x!\) 种可能构造形式，因为链翻转过来会有重复，所以我们要除以 \(2\) ，即为 \(\frac{k!}{2}\) 。
每种圆与每种链基本同理，但因为圆还可以旋转，所以为 \(\frac{(k-1)!}{2}\) 。
注意，圆只有两个点时不可旋转。
设 \(f_{i,j}\) 表示 \(i\) 点 \(j\) 边的方案数，从 \(f_{i-k,j-k}\) 与 \(f_{i-k,j-k+1}\) 转移而来，从 \(n-i+k\) 中选 \(k\) 个点，即为 \(C_{n-i+k}^{k}\)，但会有重复，我们可以利用选取一个基准点进行统计的思想，让当前最小的点一定进此连通块，为 \(C_{n-i+k-1}^{k-1}\) 。
综上，转移方程为：
初始值 \(f_{0,0}=1\) ，答案为 \(f_{n,m}\) 。
时间复杂度 \(O(nml)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=1e9+7;
long long n,m,c[605][605],a[605],mod_2,f[605][605];
long long dijah(long long x,long long y)
{
long long h=1;
while(y)
{
if(y&1)
{
h*=x;
h%=mod;
}
x*=x;
x%=mod;
y>>=1;
}
return h;
}
long long gaia(long long k)
{
memset(f,0,sizeof(f));
f[0][0]=1;
long long q;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int u=2;u<=k;u++)
{
if(u<=i&&u<=j)f[i][j]+=((f[i-u][j-u]*c[n-i+u-1][u-1]%mod)*(u>2?(a[u-1]*mod_2%mod):1)),f[i][j]%=mod;
if(u<=i&&u-1<=j)f[i][j]+=((f[i-u][j-u+1]*c[n-i+u-1][u-1]%mod)*(a[u]*mod_2%mod)),f[i][j]%=mod;
}
}
}
return f[n][m];
}
int main()
{
long long k;
c[0][0]=1;
for(int i=1;i<=600;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
a[0]=1;
for(int i=1;i<=600;i++)a[i]=(a[i-1]*i)%mod;
mod_2=dijah(2,mod-2);
scanf("%lld%lld%lld",&n,&m,&k);
printf("%lld",((gaia(k)-gaia(k-1))%mod+mod)%mod);
return 0;
}