英文题干

Define a non-empty positive integer multi-set as "Good" iff the product of all elements in the set is the square of some positive integer 𝑥, and the "Good" set has a weight of 𝑥.

Let the set 𝑆𝑆 be defined as the multi-set of all non-empty subsets of the multi-set 𝑆.

For example, when =, =

Now, given a multi-set 𝑆 of size 𝑁, Chino wants to know the sum of the weights of all "Good" sets in 𝑆𝑆. Output the answer modulo

Input:

The first line contains a positive integer — the size of 𝑆.

The next line contains positive integers — each element in the set 𝑆.

Output:

Only one line with a non-negative integer, representing the answer modulo .

中文题干

定义一个非空的正整数多重集合为“好”的条件是集合中所有元素的乘积是某个正整数 𝑥 的平方，而“好”集合的权重为 𝑥。

定义集合 𝑆𝑆 为多重集合 𝑆 的所有非空子集的多重集。

例如：当=时，=

现在，给定一个大小为 的多重集合 ，其中的元素范围 ，Chino想要知道 𝑆𝑆 中所有“好”集合的权重之和。输出答案模

思路

Inspired by 命题组，一道较为经典的质因子状压dp。

  1. 由于满足条件的子集合元素乘积为平方数，故子集中的每个质因数必然成对出现。可以将每个元素 中的质因子分为两类：小于 的（元素内可以出现多次）和大于 的（元素内只能出现一次）

  2. 首先注意到 以内质数只有 这 11 个。故对 1000 以内的数，质因子中不可能出现两个大于32的质数。可以用状态压缩（01串）进行处理（0表示某质因子在元素内出现偶数次，1表示出现奇数次）并存储状态的得分（即题中的权重）。这样就转化为01背包问题：其中背包体积为状态01串，背包价值为得分。

    记dp[i][st]为前 i 个小质数选了若干个，小质数状态压缩串为st的权值和。那么

    =

  3. 其次，对大于 的质因子，对每个大质因数分组处理。即每个包含这种质因子的元素必须同时出现偶数个。我们可以在原有 st 的基础上再加一个最高位表示这个大质因数，在分组dp后将 st 的最高位为0的保留即可。（其他的必然有奇数个质因子，没必要进行后续的其他组dp了）

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1010;

int n;
ll prime[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 0}; // 枚举小质因数，预留最后一位存大因数x

map<int, vector<pair<int, int>>> mp; // 用于存储大整数供转移
ll dp[maxn][1 << 12];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    // 构造质数01串
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;

        int st = 0;    // 当前输入元素的小质数01串
        int value = 1; // 当前元素内小质数配对后的得分

        for (int j = 0; j < 11; j++)
        {
            while (x % prime[j] == 0)
            {
                x /= prime[j];
                st ^= (1 << j);

                if ((st & (1 << j)) == 0) // 小质因数prime[i]达成配对
                    value *= prime[j];
            }
        }
        mp[x].push_back({st, value}); // 最终的x必然只剩余大质因子或1
    }

    // 进行背包dp
    dp[0][0] = 1;
    int pt = 0;
    for (auto &[x, vec] : mp) // 分组背包
    {
        prime[11] = x;
        for (auto &[st, value] : vec) // 对于每组进行01
        {
            pt++;
            if (x != 1) // 如果x是大质因数，最高位 置1
            {
                st += (1 << 11);
            }

            for (int p = 0; p < (1 << 12); p++) // 遍历大质数x所有可能的转移来源
            {
                int tmpSt = st & p; // tmpSt为1的位置就是st和p都出现奇数次的质因数（可以元素间配对）
                int tmpValue = value;
                for (int j = 0; j <= 11; j++)
                {
                    if (tmpSt & (1 << j)) // 寻找tmpSt二进制中为1的位
                    {
                        tmpValue *= prime[j]; // 原本得分*转移得分
                    }
                }

                // st^p 就是转移后的状态
                dp[pt][st ^ p] = (dp[pt - 1][st ^ p] + dp[pt - 1][p] * tmpValue) % mod;
            }
        }

        // 只保留最终转移结果最高位为0的（大质数x能完全配对），其余全部重置为0
        for (int i = (1 << 11); i < (1 << 12); i++)
        {
            dp[pt][i] = 0;
        }
    }

    cout << (dp[pt][0] - 1 + mod) % mod;

    return 0;
}