旅行没有商问题

考虑 $k=0$ 的情况
起点、终点任选，访问 $d$ 个结点，求方案数
设 $edge[x][y]$ 表示 $x,y$ 的连通情况
即 $edge[x][y]=1$ 表示存在从 $x$ 到 $y$ 的边
即 $edge[x][y]=0$ 表示不存在从 $x$ 到 $y$ 的边
设 $f[step][i]$ 表示已访问 $step$ 个结点（包含当前结点），当前位于位置 $i$ 的方案数
易得 $f[step][i]=\sum\limits_{edge[j][i]=1}f[step-1][j]$
即 $f[step][i]=\sum{f[step-1][j]*edge[j][i]}$
利用矩阵优化递推可以高效的解决这一问题
考虑 $k!=0$ 的情况，这时难以按照上述方法处理
（大佬请自动跳过）不妨考虑 $k=1$ ，必经点为 $1$
显然必经 $1$ 的方案数=不设限方案数-不经 $1$ 方案数
考虑推广容斥思路 $Ans=$ 不设限-不经必经点
设必经点集为 $\{1,2...k\},A_i$ 为经过 $i$ 点的方案集

$Ans=|\bigcap_{i=1}^kA_i|=|\bigcup|-\sum\limits_{i=1}^k|C_UA_i|+\sum\limits_{i,j=1,i>j}^k|C_UA_i\bigcap C_UA_j|-...+(-1)^k|C_UA_1\bigcap ...\bigcap C_UA_k|$
（不设限-不经一个+不经两个-...）
考虑不经点集 $S$ 下的方案数统计
1，递推边界 $f[1][A\in S]=0$
2,转移矩阵 $edge[i][A\in S]=edge[A\in S][i]=0$
就可以利用矩阵乘法高效解决这一问题了
时间复杂度 $O(2^k*n^3*logd)$