题意

原题链接
订正链接
构造一个图，图的所有边权等于$1$，求使$1$到$n$的最短路距离为$k$的方案数。
对于$ 100\text{%}$的数据$n,k \leq 100$

思路

(为了图(wo)方(tai)便(cai)，下文的$m$代表上文题意中的$k$，下文的$k$详见下文)
考虑$dp$。
因为这张图的最短路距离为$k$，所以考虑分层图。
设$f[i][j][k]$表示前$i$层总共选了$j$个，第$i$层选了$k$个。
很明显$f[0][1][1]=1$（前$0$层选$1$个，第$0$层选$1$个，因为第$0$层有一点$1$）。
暴力枚举$i,j,k,l$，分别表示前$i$层，选了$j$个，第$i$层选了$k$个，第$i-1$层选了$l$个。
${f[i][j][k]+=f[i-1][j-k][l] \times {(2^l -1)}^k \times 2^{\frac{k\times (k-1)}{2}} \times {C}_{n-j+k-1}^{k}}$

当$i=n$时，该层必须有$n$（上一个$dp$式子是必须没有$n$)。
$f[i][j][k]+=f[i-1][j-k][l] \times {(2^l -1)}^k \times 2^{\frac{k\times (k-1)}{2}} \times {C}_{n-j+k-1}^{k-1}$

${(2^l-1)}^k$: 当前层每个点至少要与上一层的一个点有边,每个点有$ 2^l -1$种连法，总共有$k$个点
$2^{\frac{k\times (k-1)}{2}} $: $k$个点之间可以互相连
$C_{n-j+k-1}^{k}$: $n-j+k$个点选$k$个的方案数，但是$n$不能选
$C_{n-j+k-1}^{k-1}$: $n-j+k$个点选$k$个的方案数，但是$n$必须选

$ans+=f[m][i][j] \times 2^{j\times (n-i)} \times 2^{\frac{(n-i)\times (n-i-1)}{2}}$

还剩$ x=n-i $个点未考虑
$2^{j\times x} $: 剩下的点可以和任何一个已经选了的点连边
$2^{\frac{x\times (x-1)}{2}} $：剩下的点之间互相连边

Code