4246: 总共花费时间恰好为K 的路径有多少条
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
# Travel
## 题目描述
小高计划进行一次旅行。有 $N$ 个城市，从城市 $i$ 到城市 $j$ 需要花费时间 $T_{i,j}$。在所有从城市1出发，访问其他所有城市恰好一次，然后返回城市1的路径中，总共花费时间恰好为 $K$ 的路径有多少条？
输入
## 输入格式
输入格式如下：
$N \ K$
$T_{1,1} ... T_{1,N}$
$⋮$
$T_{N,1} ... T_{N,N}$
输出
## 输出格式
输出一个整数表示答案。
样例输入 复制
4 330
0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0样例输出 复制
2提示
## 输入输出样例
### 输入样例1
```
4 330
0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0
```
### 输出样例1
```
2
```
### 输入样例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
```
## 数据范围与提示
【样例1说明】
有六条从城市1出发，访问所有其他城市恰好一次，然后返回城市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$。
【数据范围】
- $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$。
- 所有输入均为整数。
## 题目来源
ABC183C