路径

题目大意

有 n 个城市，任意两个之间有一定长度的路径。
然后让你从 1 号点出发不重不漏的走过每个点然后最后回到 1 号点（也就是 1 号点经过两次，其它点经过一个）。
然后问你要多少种方案是走的路径长度和恰好是 l。

思路

看着这个范围，看着这个题，不难想到可以状压 DP。

然而发现它要路径长度和恰好是 l，你要表示的话就要再加一维表示当前的路径长度，然后尽管你开 map 啊哈希啊这些搞它还是会超时。

然后你看着这个 $14$，要想到一个叫做折半搜索的东西。
我们可以枚举一个 $i$，然后把路径分成 $1\to ...\to i\to ...\to 1$ 两段。
然后由于 $i\to j$ 的费用跟 $j\to i$ 的一样，那就相当于两条 $1\to ...\to i$ 的路径满足长度相加是 $l$ 且除了 $1,i$ 没有共有的点。

然后不按你想到暴搜出每一种可能（反正只有 $7$ 步，折了半，$n!$ 都没问题），然后走的点就状压一下，然后至于权值就用哈希表。
然后就一边暴搜出来放进哈希表，一遍暴搜出来去哈希表配对。

然后就好了。

代码

#include<cstdio>
#include<cstring>
#define mo 997

using namespace std;

struct node {
	int x, to, nxt;
}e[1000001];
int n, l, a[15][15], nn, mm, zt;
int KK, hash[8192][997], now, ans;
bool in[15];

void clear_hash() {
	memset(hash, 0, sizeof(hash));
	KK = 0;
}

void hash_insert(int pl, int val) {
	int pla = val % mo;
	for (int i = hash[pl][pla]; i; i = e[i].nxt)
		if (e[i].to == val) {
			e[i].x++;
			return ;
		}
	e[++KK] = (node){1, val, hash[pl][pla]}; hash[pl][pla] = KK;
}

int hash_query(int pl, int val) {
	val = l - val;//得到你对于的另一个半的值
	pl = ((1 << (n - 1)) - 1) ^ pl;
	pl ^= (1 << (now - 1));
	int pla = val % mo;
	for (int i = hash[pl][pla]; i; i = e[i].nxt)
		if (e[i].to == val) {
			return e[i].x;
		}
	return 0;
}

void dfs(int sum, int lst, int num) {//暴搜左边一半放进哈希里面
	if (num == nn) {
		if (sum + a[lst][now] > l) return ;
		hash_insert(zt >> 1, sum + a[lst][now]);
		return ;
	}
	if (sum > l) return ;
	
	for (int i = 1; i < n; i++)
		if (!in[i]) {
			in[i] = 1;
			zt ^= (1 << i);
			dfs(sum + a[lst][i], i, num + 1);
			zt ^= (1 << i);
			in[i] = 0;
		}
}

void dfs1(int sum, int lst, int num) {//暴搜右边一半然后去哈希里面匹配
	if (num == mm) {
		if (sum + a[lst][now] > l) return ;
		ans += hash_query(zt >> 1, sum + a[lst][now]);
		return ;
	}
	if (sum > l) return ;
	
	for (int i = 1; i < n; i++)
		if (!in[i]) {
			in[i] = 1;
			zt ^= (1 << i);
			dfs1(sum + a[lst][i], i, num + 1);
			zt ^= (1 << i);
			in[i] = 0;
		}
}

int main() {
//	freopen("way.in", "r", stdin);
//	freopen("way.out", "w", stdout);
	
	scanf("%d %d", &n, &l);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &a[i][j]);
	
	nn = (n - 2) / 2;
	mm = (n - 2) - nn;
	for (now = 1; now < n; now++) {//枚举最中间是哪个点
		clear_hash();
		in[now] = 1;
		dfs(0, 0, 0);
		dfs1(0, 0, 0);
		in[now] = 0;
	}
	
	printf("%d", ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}