1381 - Balancing the Scale (技巧枚舉+位運算)

You are given a strange scale (see the figure below), and you are wondering how to balance this scale. After several attempts, you have discovered the way to balance it -- you need to put different numbers on different squares while satisfying the following two equations:

x 1  * 4 +  x 2  * 3 +  x 3  * 2 +  x 4 =  x 5 +  x 6  * 2 +  x 7  * 3 +  x 8  * 4

y 1  * 4 +  y 2  * 3 +  y 3  * 2 +  y 4 =  y 5 +  y 6  * 2 +  y 7  * 3 +  y 8  * 4

How many ways can you balance this strange scale with the given numbers?

Input 

There are multiple test cases in the input file. Each test case consists of 16 distinct numbers in the range [1, 1024] on one separate line. You are allowed to use each number only once.

A line with one single integer 0 indicates the end of input and should not be processed by your program.

Output 

For each test case, if it is possible to balance the scale in question, output one number, the number of different ways to balance this scale, in the format as indicated in the sample output. Rotations and reversals of the same arrangement should be counted only once.

Sample Input 

87 33 98 83 67 97 44 72 91 78 46 49 64 59 85 88 
0
      

Sample Output 

Case 1: 15227223      

題意：給定16個數字，求題目中給定公式的平衡方法有幾種

思路：技巧枚舉+位運算，通過位運算每次枚舉4個數字，通過全排列求出和，算出2邊相同時候狀态的種數，最後在把x的情況和y的情況數相乘并所有都相加就是答案，計算全排列前要排序一開始忘了答案一直少，後面看了題解才發現。一開始還了解錯題目了以為x和y的和都是要相同的。

代碼：

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

int num[16], st[16], Sum[(1<<16)];
vector<int> sum[22222];

bool judge(int state) {
	int sn = 0;
	for (int i = 0; i < 16; i++) {
		if (state&(1<<i))
			st[sn++] = num[i];
	}
	if (sn == 4) return true;
	return false;
}

int solve() {
	int ans = 0;
	memset(sum, 0, sizeof(sum));
	memset(Sum, 0, sizeof(Sum));
	sort(num, num + 16);
	for (int i = 0; i < (1<<16); i++) {
		if (judge(i)) {
			do {
				int s = st[0] * 4 + st[1] * 3 + st[2] * 2 + st[3];
				for (int j = 0; j < sum[s].size(); j++) {
					if ((i&sum[s][j]) == 0)
						Sum[(i|sum[s][j])]++;
				}
				sum[s].push_back(i);
			} while(next_permutation(st, st + 4));
		}
	}
	for (int k = 0; k < (1<<16); k++)
		ans += Sum[k] * Sum[k^((1<<16)-1)];
	return ans / 2;
}

int main() {
	int cas = 0;
	while (~scanf("%d", &num[0]) && num[0]) {
		for (int i = 1; i < 16; i++)
			scanf("%d", &num[i]);
		printf("Case %d: %d\n", ++cas, solve());
	}
	return 0;
}