题目描述

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

$n$个结点的环的生成树个数为$n$。

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

这两个发现让小栋欣喜若狂，由此更加坚定了他继续计算生成树个数的想法，他要计算出各种各样图的生成树数目。

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

小栋以前没有计算过这类图的生成树个数，但是，他想起了老师讲过的计算任意图的生成树个数的一种通用方法：构造一个$n \times n$的矩阵$A = \{a_{ij}\}$，其中当$i=j$时，$A_{ij} = d_i$；$i \neq j$时，$A_{ij} = -1$；其他情况$A_{ij} = 0$，其中di表示结点i的度数。

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

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

输入格式

包含两个整数$k,n$，由一个空格分隔。$k$表示要将所有距离不超过$k$的结点连接起来，$n$表示有$n$个结点。

$k \le 5, n \le 10 ^ {15}$

输出格式

输出一个整数，表示生成树的个数。由于答案可能比较大，所以你 只要输出答案除65521的余数即可。

题目解析

这题似乎用题目介绍的行列式方法分数很多？然而距离正解似乎有点遥远啊。

注意到只有距离不超过$k$的点有边相连。考虑一棵生成树，对于一个点$i$，在不考虑与$i$后面的点有关的边时，任意$j \le i - k$的点一定互相连通，且至少存在某一$j$与$[i-k+1,i]$中的某点有边相连。所以我们在构造一棵生成树时，在点$i$处向前连边时只需要考虑$[i-k,i-1]$中点的连通性。$k$很小，所以我们将$[i-k,i-1]$中点的连通性用最小表示法表示。如$k = 3$时，$1 1 1$表示三点连通；$1 2 2$表示后两点连通，但与第一个点不连通…… 经计算，可以发现在$k = 5$时合法状态数也只有52种。

我们先暴力预处理所有状态和合法的转移。令$dp(i,S)$为考虑到$i$，$[i-k+1,i]$的连通状态为$S$的方案数；$G[S][T]$为状态$T$转移到状态$S$的方案数，则有

$$dp(i,S) = \sum_{T} {dp(i-1,T) G(S,T)}$$

显然上述式子是可以用矩阵快速幂优化的。令状态数为$M$，时间复杂度为$O(M ^ 3 \log n)$。

话说代码大部分篇幅都用在预处理转移矩阵和初始值矩阵上了，难道是姿势不对？