如何高效计算从各容器取不重复元素构成的n元数组的总数量

方案1：状态压缩动态规划（适用场景：全局唯一元素总数 ≤ 20） #

这是该场景下效率最高的解法，核心逻辑是用掩码记录已经使用过的元素，避免重复计算：

• 第一步：将所有容器出现过的元素去重，给每个元素分配唯一的整数下标（比如示例中的1→0、6→1、7→2）
• 定义状态dp[i][mask]：处理完前i个容器，已使用元素对应的二进制掩码为mask时的合法方案数，mask的每一位为1代表对应下标元素已被使用
• 初始状态：dp[0][0] = 1（未处理任何容器、未使用任何元素时，方案数为1）
• 状态转移：
  遍历第i个容器的所有元素x，再遍历所有合法的mask，如果x对应的下标位不在mask中，则：
  dp[i][mask | (1 << 下标(x))] += dp[i-1][mask]
• 最终结果：所有dp[n][mask]的总和

拿示例验证：计算到第3个容器时，最终合法掩码为111（三个元素都用了），总方案数为2 + 2 = 4，和示例结果完全一致。
该方案复杂度为O(n * m * 2^k)，其中n是容器数，m是单个容器的平均长度，k是全局唯一元素总数，远低于暴力枚举的O(m^n)。

方案2：容斥原理（适用场景：全局唯一元素总数大但重复出现的元素少） #

如果全局元素很多没法用位掩码，可以用容斥原理计算：

合法总数 = Σ (-1)^t * g(t)
其中t是指定的重复元素数量，g(t)是选t个不同的元素、每个至少出现2次的所有组合对应的方案数

计算逻辑：先算不考虑重复的总组合数，减去至少有1个元素重复的方案数，加回至少有2个元素重复的方案数，以此类推即可得到最终结果。

内容的提问来源于stack exchange，提问作者display