C - Travel Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個の都市があります。都市 i から都市 j へ移動するには T_{i,j} の時間がかかります。

都市 1 を出発し、全ての都市をちょうど 1 度ずつ訪問してから都市 1 に戻るような経路のうち、移動時間の合計がちょうど K になるようなものはいくつありますか？

制約

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

入力

入力は以下の形式で標準入力から与えられる。

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

都市 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 通りです。

入力例 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 になります。

Score : 300 points

Problem Statement

There are N cities. The time it takes to travel from City i to City j is T_{i, j}.

Among those paths that start at City 1, visit all other cities exactly once, and then go back to City 1, how many paths take the total time of exactly K to travel along?

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

2

There are six paths that start at City 1, visit all other cities exactly once, and then go back to 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

The times it takes to travel along these paths are 421, 511, 330, 511, 330, and 421, respectively, among which two are exactly 330.

Sample Input 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

Sample Output 2

24

In whatever order we visit the cities, it will take the total time of 5 to travel.