bzoj5219

题意

有多少竞赛图满足从(1)出发最长路径为(k)。(kle nle 2000)

做法

令(f_{i,j})为(i)个点，(1)出发最长路径为(j)

• (j<i)
  设(1)出发最长路径的点集为(A)，剩下的为(B)，从路径尾到(1)归纳可证明(B)间(A)的方向为(Blongrightarrow A)

[f_{i,j}=f_{j,j} imes {i-1choose j-1} imes 2^{frac{(i-j)(i-j-1)}{2}} ]

• (j=i)

[f_{i,i}=2^{frac{i(i-1)}{2}}-sumlimits_{k=1}^{i-1}f_{i,k} ]