旅行路线

题目描述

有 $N$ 个城市。从城市 $i$ 移动到城市 $j$ 需要花费 $T_{i,j}$ 的时间。

在从城市 $1$ 出发、恰好访问所有城市各 $1$ 次后返回城市 $1$ 的路径中，移动时间总和恰好为 $K$ 的路径有多少条？

输入格式

输入按以下格式从标准输入给出：

$N$ $K$
$T_{1,1}$ $\ldots$ $T_{1,N}$
$\vdots$
$T_{N,1}$ $\ldots$ $T_{N,N}$

输出格式

输出答案（整数）。

样例

4 330
0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0

2

从城市 $1$ 出发、恰好访问所有城市各 $1$ 次后返回城市 $1$ 的路径有以下 $6$ 条：

• $1\to 2\to 3\to 4\to 1$
• $1\to 2\to 4\to 3\to 1$
• $1\to 3\to 2\to 4\to 1$
• $1\to 3\to 4\to 2\to 1$
• $1\to 4\to 2\to 3\to 1$
• $1\to 4\to 3\to 2\to 1$

各条路径的移动时间分别为 $421,511,330,511,330,421$，所以总和恰好为 $330$ 的路径有 $2$ 条。

5 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

24

无论按什么顺序访问城市，移动时间的总和都是 $5$。

数据范围

• $2 \leq N \leq 8$
• 当 $i \neq j$ 时 $1 \leq T_{i,j} \leq 10^8$
• $T_{i,i}=0$
• $T_{i,j}=T_{j,i}$
• $1 \leq K \leq 10^9$
• 输入均为整数