TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3126
  • 問題
  • P3126【NOI2007 Day2 T2】生成树计数
    制限 : 時間制限 : 10000 MS   メモリ制限 : 165536 KB
    問題説明

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

    入力形式

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

    出力形式

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

    サンプル入力

    3 5

    サンプル出力

    75

    ヒント



    ソース  NOI 2007 矩阵