P2109 [NOI2007]生成树计数

    • 183通过
    • 395提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 NOI系列 2007 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

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

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

    小栋以前没有计算过这类图的生成树个数,但是,他想起了老师讲过的计算任意图的生成树个数的一种通用方法:构造一个 n×n 的矩阵 A={$a_{i,j}$}

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

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

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

    输入输出格式

    输入格式:

    输入文件中包含两个整数 k, n,由一个空格分隔。k 表示要将所有距离不超过 k(含 k)的结点连接起来,n 表示有 n 个结点。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    3 5
    输出样例#1: 复制
    75

    说明

    样例对应的图如下:

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。