2024牛客暑期多校训练营2

G The Set of Squares

思路：

对于一个序列内的所有数的乘积可以分解为p₁^k1p₂^k2...p_n^kn，（p为质数）此时只有当k都为偶数时，这个序列数的乘积才为完全平方数

当在两个序列当中，所有k为奇数时对应的质数p都相同，说明这两个序列合并可以构成完全平方数

那么可以以ki的奇偶来表示某个质数的状态，k为奇数状态为1，为偶数状态为0。比如3¹的状态为1，3²的状态为0

那么p₁^k1p₂^k2...p_n^kn的状态就可以以二进制（10101000...）的形式表示

只有当两个串的每一位都相等时才能合并构成完全平方数

那么f[i]表示为序列的乘积质因子分解后的状态为i的贡献和

最后的答案即为f[0]

这里二进制表示状态的位数是有限的，可以对s根据质因子进行分类

对于一个数，最多只会存在一个质因子大于√1000，且剩下的质因子都小于√1000

可以发现小于√1000的质因子只有{2， 3， 5， 7， 11， 13，17， 19， 23， 29， 31 }共11个

那么对于一个乘积为完全平方的序列来说出现的质因子种类数最多为12，这个范围就可以用二进制表示了

可以把出现质因子大于√1000的数按最大质因子分类，质因子都小于√1000的属于一类

在分类时，求出每个数的状态和贡献（此时的贡献里不包括状态里所有k为奇数的p中，多出的那一个p，比如3³的状态为1，贡献为3（√3²带来的贡献，还多出一个3存在状态里）

所有数的状态和贡献求完后，接着就要一个一个的选数，同时转换序列状态和更新贡献

枚举选完上一个数的所有序列状态i，当前数的状态为state，将当前数加入序列后的状态转移为：now = i ^ state，贡献更新为val[i] + （i 和 state中都为1的个数，即 i & state中1的个数） 

对于最大质因子大于√1000的那类数，用的都是二进制中同一位来表示，所以每次处理完后都需要清空（因为大于√1000的质因子只会乘上自己来构成完全平方数，且每一类数的最大质因子不相同）

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int dg[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

void solve() {
    int n;
    cin >> n;
    map<int, vector<PII> > mp;
    for (int i = 1; i <= n; ++i) {
        int s;
        cin >> s;
        int state = 0, val = 1;
        for (int j = 0; j < 11; ++j) {
            if (s % dg[j] == 0) {
                while (s % dg[j] == 0) {
                    state ^= (1 << j);
                    if ((state & (1 << j)) == 0) {
                        val = val * dg[j] % Mod;
                    }
                    s /= dg[j];
                }

            }
        }
        mp[s].push_back({state, val});
    }
    vector<int> f(1 << 12);
    f[0] = 1;
    for (auto [p, vec]:mp) {
        for (auto [state, val]:vec) {
            vector<int> ff = f;
            if (p != 1) {
                state |= (1 << 11);
            }
            for (int i = 0; i < (1 << 12); ++i) {
                int now = state ^ i;
                int ans = f[i] * val % Mod;
                int ch = state & i;
                for (int j = 0; j < 11; ++j) {
                    if ((ch >> j) & 1) ans = ans * dg[j] % Mod;
                }
                if ((ch >> 11) & 1) ans = ans * p % Mod;
                ff[now] = (ff[now] + ans) % Mod;
            }
            f = ff;
        }
        for (int i = 1 << 11; i < (1 << 12); ++i) f[i] = 0;
    }
    cout << f[0] - 1;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}