AT_abc183_c [ABC183C] Travel

题目描述

小高计划进行一次旅行。有 $N$ 个城市，从城市 $i$ 到城市 $j$ 需要花费时间 $T_{i,j}$。在所有从城市 $1$ 出发，访问其他所有城市恰好一次，然后返回城市 $1$ 的路径中，总共花费时间恰好为 $K$ 的路径有多少条？

输入格式

输入共 $N+1$ 行。

第一行输入两个正整数 $N,K$，中间以单个空格隔开。

然后输入一个 $N \times N$ 的矩阵，第 $i$ 行第 $j$ 列上的数为 $T_{i,j}$。

输出格式

输出一个整数表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #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→2→3→4→1$
• $1→2→4→3→1$
• $1→3→2→4→1$
• $1→3→4→2→1$
• $1→4→2→3→1$
• $1→4→3→2→1$

这些路径的总花费时间分别为 $421, 511, 330, 511, 330$ 和 $421$，其中恰好有两条路径的总花费时间为 $330$。

样例 2 解释

无论以何种顺序访问城市，总花费时间都是 $5$。

数据范围

• $2 \le N \le 8$；
• 对于 $i \ne j$，$1 \le t_{i,j} \le 10^8$
• $T_{i,i}=0,T_{i,j}=T_{j,i}$
• $1 \le K \le 10^9$；
• 输入中的所有值均为整数。