三校集训Part2 NBCX Day7 timegate 题解

题意

原题链接
订正链接
构造一个图,图的所有边权等于$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

暂无评论

发送评论


				
上一篇
下一篇