记录编号	39307	评测结果	EEEEEEEEEE
题目名称	项链制作	最终得分	0
用户昵称	CC	是否通过	未通过
代码语言	C++	运行时间	1.026 s
提交时间	2012-07-08 17:47:32	内存使用	4.11 MiB

#include <cstdio> 
#include <algorithm> 
#include <cstring> 
int n,mm; 
int c[20][20],dd[20],f[500000],g[500000];
int prepare(int u) {
	int tmp = 1;
	for (int i = 1;i <= n;i++) 
		if (dd[i] & u) 
			for (int j = i + 1;j <= n;j++) 
				if (dd[j] & u) 
					tmp *= (c[i][j] + 1);
	return tmp;
}
int dp(int u) {
	if (g[u]) return g[u];
	int minu,tmp = 0;
	for (minu = 1;;minu++) if (dd[minu] & u) break;
	u ^= dd[minu];
	if (u == 0) return g[dd[minu]] = 1;
	for (int i = (u - 1) & u;;(--i) &= u) {
		tmp += dp(i + dd[minu]) * f[u ^ i];
		if (i == 0) break;
	}
	return g[u |= dd[minu]] = f[u] - tmp;
}

int main() {
	freopen("necklace.in","r",stdin);
	freopen("necklace.out","w",stdout);
	scanf("%d", &n);
	mm = (1 << n) - 1;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++) scanf("%d", &c[i][j]);
	dd[1] = 1;
	for (int i = 2;i <= n;i++) dd[i] = dd[i - 1] << 1;
	for (int i = 1;i <= mm;i++) f[i] = prepare(i);
	printf("%d\n",dp(mm));
	return 0;
}