分数: 300 点
问题陈述
有 N 城市。从 City 出发所需时间 i 前往城市 j is T_{i, j}.
在从 City 开始的路径中 1,访问所有其他城市一次,然后返回 City 1,有多少条路径总共花费了 K 一起旅行?
约束
- 2\leq N \leq 8
- If 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
T_{1,1} \ldots T_{1,N}
\vdots
T_{N,1} \ldots T_{N,N}
输出
将答案打印为整数。
示例输入 1
4 330 0 1 10 100 1 0 20 200 10 20 0 300 100 200 300 0
示例输出 1
2
有 6 条路径从 City 开始 1,访问所有其他城市一次,然后返回 City 1:
- 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
示例输出 2
24
无论我们以什么顺序访问这些城市,总时间将是 5 去旅行。