本题没有可用的提交语言。

题目描述

你得到了一个奇怪的天平（见下图），想知道如何让它平衡。经过多次尝试，你发现平衡的方法是：在不同的方格中放置不同的数字，同时满足以下两个方程：

给定一组16个不同的数字（范围在[1, 1024]之间），每个数字只能使用一次。问有多少种不同的方式可以使天平平衡？注意：相同排列的旋转或翻转视为同一种方式，仅计数一次。

输入格式

• 输入包含多个测试用例，每个测试用例占一行，包含16个不同的整数。
• 输入以一行单独的0结束，该行无需处理。

输出格式

• 对每个测试用例，若存在平衡方式，输出满足条件的不同方式数，格式如样例所示。
• 若不存在平衡方式，输出0。

输入输出样例

输入数据 1

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

输出数据 1

Case 1: 15227223  

题目来源

Shanghai 2006

关键分析

1. 天平结构建模：

   • 左右两侧各有8个位置，每个位置对应不同的权重（如左侧x1的权重为4，x2为3等）。
   • 需将16个数字分配到16个位置，使左右两侧的加权和分别相等（两个方程同时满足）。

2. 去重规则：

   • 若两种排列可通过旋转或翻转相互转换，则视为同一种方式。需设计算法避免重复计数。

3. 暴力枚举优化：

   • 直接枚举16!种排列显然不可行，需通过剪枝、分组计算权重和、利用对称性等方法优化。

4. 数学转化：

   • 将问题转化为求解两个加权和方程的解，其中每个变量取唯一的数字，且需考虑排列的对称性去重。