[ABC183C] Travel

题面翻译

题目描述

有 $n$ 个城市，从城市 $i$ 到城市 $j$ 需要的时间为 $t_{i,j}$。请问：从城市 $1$ 开始，只访问其他城市一遍，最后返回城市 $1$ 的路径中，有多少条路径所需要的时间为 $k$？

输入格式

输入共 $(n+1)$ 行。第一行输入两个正整数 $n,k$，中间以单个空格隔开；然后输入一个 $n \times n$ 的矩阵，第 $i$ 行第 $j$ 列上的数为 $t_{i,j}$。

输出格式

输出一行一个非负整数，即满足条件的路径条数。

说明/提示

数据规模与约定

所有输入数据保证：

• $2 \le n \le 8$；
• 对于所有满足$1 \le i,j \le n$ 且 $i \neq j$ 的整数对 $(i,j)$，$t_{i,i}=0,t_{i,j}=t_{j,i},1 \le t_{i,j} \le 10^8$；
• $1 \le k \le 10^9$；
• 输入中的所有值均为整数。

题目描述

$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}$

输出格式

答えを整数で出力せよ。

样例 #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

提示

制約

• $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$
• 入力はすべて整数

Sample Explanation 1

都市 $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$
• の $6$ 通りがあります。それぞれの移動時間は、$421,511,330,511,330,421$ なので、ちょうど $330$ であるようなものは $2$ 通りです。

Sample Explanation 2

どのような順で都市を訪問しても、移動時間の合計は $5$ になります。