1381 Balancing the Scale：技巧枚舉 + 位運算優化

題目大意

給定 16 個互不相同的數（1~1024），放入天平兩側各 8 個位置，滿足加權和相等：
左：x1*4 + x2*3 + x3*2 + x4 = 右：y1 + y2*2 + y3*3 + y4*4
左：y1*4 + y2*3 + y3*2 + y4 = 右：x1 + x2*2 + x3*3 + x4*4
求平衡方案數，旋轉/翻轉視為同一方案。

解法：分治枚舉 + 位掩碼去重

16 個數分為左右兩組各 8 個，每組內再分為兩側各 4 個。枚舉左組 4 個數的所有排列（4! = 24），計算加權和 s，記錄狀態掩碼。對每個和 s，統計有多少個不重疊的掩碼對。同理處理右組。最終將左右相同和的方案數相乘並求和，除以 2（去除左右對稱重複）。

關鍵優化

• 預先排序 16 個數，枚舉組合時用 next_permutation 生成排列，自動去重。
• 用位掩碼 (1<<16) 表示選取的數，快速判斷不重疊：(mask1 & mask2) == 0。
• 用數組 sum[s] 存儲產生和 s 的所有掩碼，Sum[mask] 記錄與 mask 不重疊且和相同的方案數。

代碼框架

int num[16], st[4];
vector masks[20000]; // 按和存掩碼
int cnt[1<<16];           // 記錄不重疊對數

bool gen(int mask) { /* 取出 4 個數到 st */ }

int solve() {
    sort(num, num+16);
    for (int mask = 0; mask < (1<<16); ++mask)
        if (gen(mask)) {
            do { int s = st[0]*4 + st[1]*3 + st[2]*2 + st[3];
                for (int m : masks[s]) if ((m & mask) == 0) cnt[mask | m]++;
                masks[s].push_back(mask);
            } while (next_permutation(st, st+4));
        }
    long long ans = 0;
    for (int mask = 0; mask < (1<<16); ++mask)
        ans += 1LL * cnt[mask] * cnt[mask ^ ((1<<16)-1)];
    return ans / 2;
}

複雜度

枚舉 C(16,4)=1820 個組合，每組 24 個排列，總操作 ~4 萬次，極快。