2024牛客暑期多校训练营（DP补题）

IR101 · 2024-07-25 10:06:56 · 个人记录

G.The Set of Squares

题意：给一个多重集合，好集合的定义是，集合中元素的乘积为平方数，问子集中好集合的开方的和

思路：可以发现，好集合其实就是，质因子分解之后，集合的每个质因子的个数都是偶数个，我们又可以发现，对于一个数字来说，他的某个质因子有多个，那么一定是小于<=31的，我们先考虑数字只有这种小质因子的那些如何求解，我们发现对于每一个质因子的答案我们可以单独拿出来，我们设这把这11个质因子状态压缩：0代表当前状态下，这一个质因子的个数为偶数个，1代表为奇数个，，我们01背包来决定某个数字选或者不选，状态不多,1000多个，选了对状态的影响就是异或之后的，贡献是本身的所有质因子/2的贡献，乘那些1变为0的贡献，然后再乘上一个状态的贡献，当然也可以不选，加上前一个的本状态即可。那么我们处理完小质数的，对于大质数，37 43 ，这种，每个数字最多贡献一个，那么我们直接按照大质数分组，每组进行01背包选择，我们最后能够保留推到下一层的一定是大质数那一位是0的，最后答案减去1，因为加了一个F[0][0]=1多余的

diamond：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1003
#define LD (o<<1)
#define RD (o<<1|1)
const int mod=1e9+7;
#define PII pair<int,int>
int a[N];
int prime[13]={2,3,5,7,11,13,17,19,23,29,31};
int f[N][(1<<12)];
map<int,vector<PII>>mp;
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        int d = a[i];
        int sz = 0;
        int sum = 1;
        for (int j = 0; j < 11; ++j) {
            int cnt = 0;
            while (d % prime[j] == 0) {
                cnt++;
                d /= prime[j];
            }
            sum *= pow(prime[j], cnt / 2);
            if (cnt & 1) {
                sz += (1 << j);
            }
        }
        mp[d].push_back({sz, sum});
    }
    f[0][0] = 1;
    int m;
    for(auto &[v,b]:mp) {
        if (v == 1) {
             m = b.size();
            for (int i = 1; i <= m; ++i) {
                auto [zt, res] = b[i - 1];
                for (int j = 0; j < (1 << 11); ++j) {
                    f[i][j] = f[i - 1][j];
                    f[i][j] %= mod;
                    int sm = 1;
                    for (int k = 0; k < 11; ++k) {
                        if (((zt ^ j) >> k)&1 and ((j >> k) & 1) == 0) {
                            sm *= prime[k];
                        }
                    }
                    f[i][j] += f[i - 1][j ^ zt] * sm%mod*res%mod;
                    f[i][j] %= mod;
                }
            }
            for (int i = 0; i <(1<<11) ; ++i) {
                f[0][i]=f[m][i];
            }
        }
        else{
            m = b.size();
            prime[11]=v;
            for (int i = 1; i <= m; ++i) {
                auto [zt, res] = b[i - 1];
                zt+=(1<<11);
                for (int j = 0; j < (1 << 12); ++j) {
                    f[i][j] = f[i - 1][j];
                    f[i][j] %= mod;
                    int sm = 1;
                    for (int k = 0; k < 12; ++k) {
                        if (((zt ^ j) >> k)&1 and ((j >> k) & 1) == 0) {
                            sm *= prime[k];
                        }
                    }
                    f[i][j] += f[i - 1][j ^ zt] * sm%mod*res%mod;
                    f[i][j] %= mod;
                }
            }
            for (int i = 0; i <(1<<11) ; ++i) {
                f[0][i]=f[m][i];
            }
        }
    }
    cout<<(f[m][0]-1+mod)%mod<<endl;

        return 0;
}