Type: Default 1000ms 256MiB

[ABC183C] Travel

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC183C] Travel

题面翻译

题目描述

nn 个城市,从城市 ii 到城市 jj 需要的时间为 ti,jt_{i,j}。请问:从城市 11 开始,只访问其他城市一遍,最后返回城市 11 的路径中,有多少条路径所需要的时间为 kk

输入格式

输入共 (n+1)(n+1) 行。第一行输入两个正整数 n,kn,k,中间以单个空格隔开;然后输入一个 n×nn \times n 的矩阵,第 ii 行第 jj 列上的数为 ti,jt_{i,j}

输出格式

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

说明/提示

数据规模与约定

所有输入数据保证:

  • 2n82 \le n \le 8
  • 对于所有满足1i,jn1 \le i,j \le niji \neq j 的整数对 (i,j)(i,j)ti,i=0,ti,j=tj,i,1ti,j108t_{i,i}=0,t_{i,j}=t_{j,i},1 \le t_{i,j} \le 10^8
  • 1k1091 \le k \le 10^9
  • 输入中的所有值均为整数。

题目描述

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

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

输入格式

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

N N K K T1,1 T_{1,1} \ldots T1,N T_{1,N} \vdots TN,1 T_{N,1} \ldots TN,N 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 N  8 2\leq\ N\ \leq\ 8
  • i j i\neq\ j のとき 1 Ti,j  108 1\leq\ T_{i,j}\ \leq\ 10^8
  • Ti,i=0 T_{i,i}=0
  • Ti,j=Tj,i T_{i,j}=T_{j,i}
  • 1 K  109 1\leq\ K\ \leq\ 10^9
  • 入力はすべて整数

Sample Explanation 1

都市 1 1 を出発し、全ての都市をちょうど 1 1 度ずつ訪問してから都市 1 1 に戻るような経路は、

  • 1 2 3 4 1 1\to\ 2\to\ 3\to\ 4\to\ 1
  • 1 2 4 3 1 1\to\ 2\to\ 4\to\ 3\to\ 1
  • 1 3 2 4 1 1\to\ 3\to\ 2\to\ 4\to\ 1
  • 1 3 4 2 1 1\to\ 3\to\ 4\to\ 2\to\ 1
  • 1 4 2 3 1 1\to\ 4\to\ 2\to\ 3\to\ 1
  • 1 4 3 2 1 1\to\ 4\to\ 3\to\ 2\to\ 1
  • 6 6 通りがあります。それぞれの移動時間は、421,511,330,511,330,421 421,511,330,511,330,421 なので、ちょうど 330 330 であるようなものは 2 2 通りです。

Sample Explanation 2

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

训练题单三

Not Claimed
Status
Done
Problem
10
Open Since
2024-10-11 0:00
Deadline
2024-10-26 23:59
Extension
24 hour(s)