4246: Travel

# Travel ### 内存 1024MB ### 时间 2S ## 题目描述 小高计划进行一次旅行。有 $N$ 个城市，从城市 $i$ 到城市 $j$ 需要花费时间 $T_{i,j}$。在所有从城市1出发，访问其他所有城市恰好一次，然后返回城市1的路径中，总共花费时间恰好为 $K$ 的路径有多少条？ ## 输入格式 输入格式如下： $N \ K$ $T_{1,1} ... T_{1,N}$ $⋮$ $T_{N,1} ... T_{N,N}$ ## 输出格式 输出一个整数表示答案。 ## 输入输出样例 ### 输入样例1 ``` 4 330 0 1 10 100 1 0 20 200 10 20 0 300 100 200 300 0 ``` ### 输出样例1 ``` 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 \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$ 这些路径的总花费时间分别为 $421$, $511$, $330$, $511$, $330$, 和 $421$，其中恰好有两条路径的总花费时间为 $330$。 【样例2说明】 无论以何种顺序访问城市，总花费时间都是 $5$。 【数据范围】 - $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$。 - 所有输入均为整数。 ## 题目来源 ABC183C