\(\text{Solution}\)
\(30\) 分暴搜合法路径
另 \(30\) 分状压
设 \(f_{i,j,k}\) 表示当前到第 \(i\) 个点，走过的点状态为 \(j\)，走过的路径长度为 \(k\) 的方案数
\(100\) 分仍然回到暴搜
考虑折半搜索，把路径拼起来，先搜一次，哈希表记下 \(f_{i,j,k}\)，再搜一次，因为是无向图，可以都从 \(1\) 开始，统计答案
\(\text{Code}\)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include<cstdio>
#define re register
using namespace std;
typedef long long ll;
const int mod = 19260817;
int n, l, ans, a[20][20], lim, MS;
struct node{
int x, s, len, nxt, f;
}e[mod + 5];
int h[mod + 5], tot;
inline void modify(int x, int s, int len)
{
int key = (21474836470000ll * x + 1000000007ll * s + 1009ll * len) % mod;
for(re int i = h[key]; i; i = e[i].nxt)
if (e[i].x == x && e[i].s == s && e[i].len == len) return (void)++e[i].f;
e[++tot] = node{x, s, len, h[key], 1}, h[key] = tot;
}
inline int query(int x, int s, int len)
{
int key = (21474836470000ll * x + 1000000007ll * s + 1009ll * len) % mod;
for(re int i = h[key]; i; i = e[i].nxt)
if (e[i].x == x && e[i].s == s && e[i].len == len) return e[i].f;
return 0;
}
void dfs1(int x, int s, int len, int num)
{
if (num >= lim) return modify(x, s, len);
for(re int i = 2; i <= n; i++)
if (!((s >> (i - 1)) & 1) && len + a[x][i] <= l)
dfs1(i, s + (1 << (i - 1)), len + a[x][i], num + 1);
}
void dfs2(int x, int s, int len, int num)
{
if (num >= n - lim)
return void(ans += query(x, (MS ^ (s - (1 << (x - 1)))) - 1, l - len));
for(re int i = 2; i <= n; i++)
if (!((s >> (i - 1)) & 1) && len + a[x][i] <= l)
dfs2(i, s + (1 << (i - 1)), len + a[x][i], num + 1);
}
int main()
{
freopen("way.in", "r", stdin);
freopen("way.out", "w", stdout);
scanf("%d%d", &n, &l);
for(re int i = 1; i <= n; i++)
for(re int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
lim = n >> 1, MS = (1 << n) - 1, dfs1(1, 0, 0, 0), dfs2(1, 0, 0, 0);
printf("%d", ans);
}