

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.