POJ 3139 Balancing the Scale

Description

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:

x1 * 4

+

x2 * 3

+

x3 * 2

+

x4

=

x5

+

x6 * 2

+

x7 * 3

+

x8 * 4

y1 * 4

+

y2 * 3

+

y3 * 2

+

y4

=

y5

+

y6 * 2

+

y7 * 3

+

y8 * 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

算有多組答案，先根據數值的範圍可以知道，最大值不會超過10240。

先用四個數組成全部的情況，總共有4!*C(16,4)種，用連結清單分别對應到相應的值上。

然後對于同一個值，計算出對應的8個數的組合，用狀壓統計到數組裡

然後兩個互補的8個數組合相乘就是答案。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 9973;
const int N = 1 << 16;
int a[16], b[4], c[4], cas = 0;
int ft[N], nt[N], u[N], sz;
int f[N];

void get(int x, int y, int z)
{
  if (x == 4)
  {
    rep(i, 0, 3) c[i] = b[i];
    do
    {
      int C = 0;
      rep(i, 0, 3) C += a[c[i]] * (4 - i);
      u[sz] = z; nt[sz] = ft[C]; ft[C] = sz++;
    } while (next_permutation(c, c + 4));
  }
  else rep(i, y, 15)
  {
    b[x] = i;
    get(x + 1, i + 1, z | (1 << i));
  }
}

int main()
{
  while (scanf("%d", &a[0]) != EOF, a[0])
  {
    rep(i, 1, 15) scanf("%d", &a[i]);
    rep(i, 0, N) ft[i] = -1;
    sz = 0;  get(0, 0, 0);
    memset(f, 0, sizeof(f));
    rep(i, 0, N)
    {
      loop(j, ft[i], nt)
      {
        loop(k, nt[j], nt)
        {
          if (u[j] & u[k]) continue;
          f[u[j] | u[k]]++;
        }
      }
    }
    LL ans = 0;
    rep(i, 0, (1 << 16) - 1)
    {
      ans += 1LL * f[i] * f[((1 << 16) - 1) ^ i];
    }
    printf("Case %d: %lld\n", ++cas, ans / 2);
  }
  return 0;
}