304446: CF848D. Shake It!
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Shake It!
题意翻译
给定 $n,m$,现在按照此规则生成无向图,初始我们有一张图 $G$,仅包含两个节点 $s,t$,以及连接 $s\to t$ 的边。 每次你可以选择一条已经存在的边 $(u,v)$,然后将往图中加入节点 $w$ 和边 $(u,w),(w,v)$,这样操作 $n$ 次,我们将得到一张图 $G'$ 定义 $G'$ 合法,当且仅当 $\textrm{mincut}(s,t)=m$,即 $s\to t$ 的最小割为 $m$ 求本质不同的合法的图 $G'$ 的数量,答案对 $10^9+7$ 取模。 其中,两张图 $G_1,G_2$ 不同,当且仅当不存在一种作用于点集的置换,使得边对应相同,同时 $s,t$ 对应相同。 $n,m\le 50$ translated by EmptySoulist题目描述
A never-ending, fast-changing and dream-like world unfolds, as the secret door opens. A world is an unordered graph $ G $ , in whose vertex set $ V(G) $ there are two special vertices $ s(G) $ and $ t(G) $ . An initial world has vertex set $ {s(G),t(G)} $ and an edge between them. A total of $ n $ changes took place in an initial world. In each change, a new vertex $ w $ is added into $ V(G) $ , an existing edge $ (u,v) $ is chosen, and two edges $ (u,w) $ and $ (v,w) $ are added into $ E(G) $ . Note that it's possible that some edges are chosen in more than one change. It's known that the capacity of the minimum $ s $ - $ t $ cut of the resulting graph is $ m $ , that is, at least $ m $ edges need to be removed in order to make $ s(G) $ and $ t(G) $ disconnected. Count the number of non-similar worlds that can be built under the constraints, modulo $ 10^{9}+7 $ . We define two worlds similar, if they are isomorphic and there is isomorphism in which the $ s $ and $ t $ vertices are not relabelled. Formally, two worlds $ G $ and $ H $ are considered similar, if there is a bijection between their vertex sets ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF848D/74c8e824289748b1c6091efe47efb3bcb1171b41.png), such that: - $ f(s(G))=s(H) $ ; - $ f(t(G))=t(H) $ ; - Two vertices $ u $ and $ v $ of $ G $ are adjacent in $ G $ if and only if $ f(u) $ and $ f(v) $ are adjacent in $ H $ .输入输出格式
输入格式
The first and only line of input contains two space-separated integers $ n $ , $ m $ ( $ 1<=n,m<=50 $ ) — the number of operations performed and the minimum cut, respectively.
输出格式
Output one integer — the number of non-similar worlds that can be built, modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
3 2
输出样例 #1
6
输入样例 #2
4 4
输出样例 #2
3
输入样例 #3
7 3
输出样例 #3
1196
输入样例 #4
31 8
输出样例 #4
64921457