TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3126
  • Problem
  • P3126【NOI2007 Day2 T2】生成树计数
    Limits : Time Limit : 10000 MS   Memory Limit : 165536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    3 5

    Sample Output

    75

    Hint



    Source  NOI 2007 矩阵