hdu5765 고차원 접두사 및

이 문제의 주요 난점은 고차원 접두사와 물론 서브맵의 연결성에 관한 문제도 있다. 사실은 매우 간단한 dp이다. 이 방면의 지식을 잘 모르면 hdu5713을 만들 수 있다.
지금 바로 고차원 접두어와:
우선 간단한 두 개의 접두사와 문자열hash종에서 흔히 볼 수 있는
예를 들어(0,0)~(1,1)
되다
(0,0)  (1,0)
 (0,1) (1,1)
그래서 dp[1][1]=value[0]+value[1][0]+value[0]][1]+value[1];
dp[1][0]=value[0][0]+value[1][0];dp[0][1]=value[0][0]+value[0][1];
dp[0][0]=value[0][0];
우리가 어떻게 사용해서 추가했는지 기억해 보자. 우선 우리는 먼저 dp열이다.
dp[0][0]=value[0][0],dp[1][0]=value[1][0],
dp[0][1]=value[0][0]+value[0][1],
dp[1][1]=value[1][0]+value[1][1];
이어서 dp행
dp[1][1]+=dp[0][1];
dp[1][0]+=dp[0][0];
마찬가지로 우리는 이 방법을 넓힐 수 있다
두 자리에 있을 때 먼저 x축, 그리고 y축
그러면 3차원은 x축, y축, 그리고 z축이 될 수 있다.
이렇게 계속하면 고차원 접두사와
접두사
dp[1][1][x][1][1][1]
이 dp[1][1][x][1][1] 값은 dp[][][][]의 모든 dp값의 합을 포함한다

#include
#include
#include
using namespace std;
int t, n, m;
bool isconnected[2000200];
struct edgee
{
	int from, to;
};
edgee rem[500];
int edge[500];
int dp[2000200],value[1000];
int main()
{
	scanf("%d", &t);
	int k = 1;
	while (t--)
	{
		scanf("%d%d", &n, &m);
		for (int i = 0; i <400; i++)
			value[i] = 0;
		for (int i = 0; i < n; i++)
			edge[i] = 0;
		for (int i = 0; i < m; i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			edge[a] |= (1 << b);
			edge[b] |= (1 << a);
			rem[i].from = a; rem[i].to = b;
		}
		int sum = 1 << n;
		for (int i = 1; i < sum; i++)
			isconnected[i] = 0,
		       dp[i]=0;
		for (int i = 0; i < n; i++)
		{
			int ss = 1 << i;
			isconnected[ss] = 1;
		}
		for (int i = 1; i < sum; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (isconnected[i] == 1)
					break;
				int kk = 1 << j;
				if ((i&kk) == 0)
					continue;
				int tempp = kk^i;
				if (isconnected[tempp] == 0)
					continue;
				if (edge[j] & tempp)
					isconnected[i] = 1;
			}
		}
		for (int i = 1; i < sum; i++)
		{
			int another = (sum-1) - i;
			if (isconnected[i] && isconnected[another])
				dp[i] = 1;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 1; j < sum; j++)
			{
				int kk = 1 << i;
				if (kk&j)
					continue;
				int tempp = j | kk;
				dp[tempp] += dp[j];
			}
		}
		for (int i = 0; i < m; i++)
		{
			int a = rem[i].from; int b = rem[i].to;
			int temp1 = 1 << a; int temp2 = 1 << b;
			int temp3 = 0;
			for (int j = 0; j < n; j++)
			{
				if (j == a || j == b)
					continue;
				temp1 |= (1 << j); temp2 |= (1 << j);
				temp3 |= (1 << j);
			}
			value[i] = dp[temp1] + dp[temp2] - 2 * dp[temp3];
		}
		printf("Case #%d: ", k++);
		for (int i = 0; i