ABC180F Unbranched

, ,

警戒！真的不会计数了。/kk

显然对 $L$ 差分。度数不超过 $2$，说明只有链或者环。

令 $f_{i,j}$ 表示现在已经有了 $i$ 个点 $j$ 条边的方案数，考虑枚举新一个连通块的大小进行转移。

直接转移显然要算重。我们不想算重的一个办法就是让加入的东西有顺序。一种是让每次加入的连通块的数目不降，但是这样复杂度会爆炸。

此时我们只需要钦定剩下 $n-i+k$ 个点中，编号最小的点在新的连通块，这样我们算出来的东西就有序了。具体的，乘上系数 $\dbinom{n-i+k-1}{k-1}$。

其他就是乘上环的系数和链的系数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 305
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
inline int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int f[maxn][maxn],n,m,k;
int suf[maxn],isuf[maxn];
const int inv2=(1+mod)/2;
int C(int x,int y) {return suf[x]*isuf[y]%mod*isuf[x-y]%mod;}
void add(int &x,int y) {x=(x+y)%mod;}
int solve(int K) {
    int i,j,k;
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for (i=1;i<=n;i++) {
        for (j=0;j<=m;j++) {
            for (k=1;k<=K;k++) {
                if (j>=k-1&&i>=k) {
                    if (k>1) add(f[i][j],f[i-k][j-k+1]*C(n-i+k-1,k-1)%mod*suf[k]%mod*inv2);
                    else add(f[i][j],f[i-k][j-k+1]*C(n-i+k-1,k-1)%mod*suf[k]%mod);
                }
                if (j>=k&&i>=k&&k>1) {
                    if (k>2) add(f[i][j],f[i-k][j-k]*C(n-i+k-1,k-1)%mod*suf[k-1]%mod*inv2);
                    else add(f[i][j],f[i-k][j-k]*C(n-i+k-1,k-1)%mod*suf[k-1]%mod);
                }
            }
            // gdb(i,j,f[i][j]);
        }
    }
    return f[n][m];
}
signed main(void){
	int i;
    read(n);read(m);read(k);
    for (suf[0]=1,i=1;i<=n;i++) suf[i]=suf[i-1]*i%mod;
    for (isuf[n]=power(suf[n]),i=n;i>=1;i--) isuf[i-1]=isuf[i]*i%mod;
    printf("%lld\n",(solve(k)-solve(k-1)+mod)%mod);
    return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i