1153: #2356. 「NOI2007」 生成树计数

最近，小栋在无向连通图的生成树个数计算方面有了惊人的进展，他发现：

• $n$ 个结点的环的生成树个数为 $n$ 。
• $n$ 个结点的完全图的生成树个数为 nn−2n^{n-2}n​n−2​​ 。

这两个发现让小栋欣喜若狂，由此更加坚定了他继续计算生成树个数的想法，他要计算出各种各样图的生成树数目。
一天，小栋和同学聚会，大家围坐在一张大圆桌周围。小栋看了看，马上想到了生成树问题。如果把每个同学看成一个结点，邻座（结点间距离为 $1$ ）的同 学间连一条边，就变成了一个环。可是，小栋对环的计数已经十分娴熟且不再感兴趣。于是，小栋又把图变了一下：不仅把邻座的同学之间连一条边，还把相隔 一个座位（结点间距离为 $2$ ）的同学之间也连一条边，将结点间有边直接相连的这两种情况统称为有边相连，如 图 1 所示。

小栋以前没有计算过这类图的生成树个数，但是，他想起了老师讲过的计算任意图的生成树个数的一种通用方法：
构造一个 $n\times n$ 的矩阵 A={aij}A=\{a_{ij}\}A={a​ij​​} ，其中：

$$a_{ij}=\{\begin{array}{cc}{d}_i& i=j\\ -1& (i,j)\in V\\ 0& (i,j)\notin V& i\ne j\end{array}$$

其中 did_id​i​​ 表示结点 $i$ 的度数。与 图 1 相应的 $A$ 矩阵如下所示。为了计算 图 1 所对应的生成数的个数，只要去掉矩阵 $A$ 的最后一行和最后一列，得到一个$(n-1)\times (n-1)$ 的矩阵 $B$ ，计算出矩阵 $B$ 的行列式的值，便可得到 图 1 的生成树的个数。

$$\text{A}=\begin{array}{cccccccc}4& -1& -1& 0& 0& 0& -1& -1\\ -1& 4& -1& -1& 0& 0& 0& -1\\ -1& -1& 4& -1& -1& 0& 0& 0\\ 0& -1& -1& -4& -1& -1& 0& 0\\ 0& 0& -1& -1& 4& -1& -1& 0\\ 0& 0& 0& -1& -1& 4& -1& -1\\ -1& 0& 0& 0& -1& -1& 4& -1\\ -1& -1& 0& 0& 0& -1& -1& 4\end{array}\text{B}=\begin{array}{ccccccc}4& -1& -1& 0& 0& 0& -1\\ -1& 4& -1& -1& 0& 0& 0\\ -1& -1& -4& -1& -1& 0& 0\\ 0& -1& -1& 4& -1& -1& 0\\ 0& 0& -1& -1& -4& -1& -1\\ 0& 0& 0& -1& -1& -4& -1\\ -1& 0& 0& 0& -1& -1& -4\end{array}$$

所以生成树的个数为 $|B|=3528$ 。小栋发现利用通用方法，因计算过于复杂而很难算出来，而且用其他方法也难以找到更简便的公式进行计算。于是，他将图做了简化，从一个地方将圆桌断开，这样所有的同学形成了一条链，连接距离为 $1$ 和距离为 $2$ 的点。例如八个点的情形如下：

这样生成树的总数就减少了很多。小栋不停的思考，一直到聚会结束，终于找到了一种快捷的方法计算出这个图的生成树个数。可是，如果把距离为 $3$ 的点也连起来，小栋就不知道如何快捷计算了。现在，请你帮助小栋计算这类图的生成树的数目。

输入格式

输入中包含两个整数 $k,n$ ，由一个空格分隔。 $k$ 表示要将所有距离不超过 $k$ （含 $k$ ）的结点连接起来， function transform(){ let height=document.body.clientHeight; let width=parseInt(document.body.clientWidth*0.6); let width2=parseInt(document.body.clientWidth*0.4); let submitURL=$("#submit")[0].href; console.log(width); let main=$("#main"); let problem=main.html(); if (window.screen.width < 500){ main.parent().append("

"); $("#submitPage").html(""); window.setTimeout('$("#ansFrame")[0].scrollIntoView()',1000); }else{ main.removeClass("container"); main.css("width",width2); main.css("margin-left","10px"); main.parent().append(""); $("#submitPage").html(""); } $("#submit").remove(); } function submit_code() { if (!$('#submit_code input[name=answer]').val().trim() && !editor.getValue().trim()) return false; $('#submit_code input[name=language]').val($('#languages-menu .item.active').data('value')); lastSubmitted = editor.getValue(); $('#submit_code input[name=code]').val(editor.getValue()); return true; } // $('#languages-menu')[0].scrollTop = $('#languages-menu .active')[0].offsetTop - $('#languages-menu')[0].firstElementChild.offsetTop; $(function () { $('#languages-menu .item').click(function() { $(this) .addClass('active') .closest('.ui.menu') .find('.item') .not($(this)) .removeClass('active') ; editor.getSession().setMode("ace/mode/" + $(this).data('mode')); }); });