526互联

C. Square Subsets 线性基

发布时间 2023-09-14 00:42:12作者: 久远寺冇珠

 题意：给出n个数字，我们成一个不为空的子序列为好，当其内所有元素乘积为一个完全平方数的时候。问有多少好的子序列。

做法：我发现给出的样例结果很有意思。，都是2的k次方减1。

 对于一个数，根据算数基本定理，可以得出，我们把素因子抽象为线代中的秩。于是子序列中的相乘，就等于该维度上的相加。可以得出一个有趣的结论，对于一个子序列，当所有秩上的数之和为一个偶数，那么他就是完全平方数，否则就不是。而奇偶是交替出现的，我们可以用异或来代替，那么做法呼之欲出了，就是线性基。剩下的就是数据范围的考虑，，这个范围里只有19个素数，不会爆longlong（会爆的话我就换种写法），非常契合我们的线性基。

vector<ll>B;
void insert(ll x){
    for(auto &b:B)x=min(x,b^x);
    for(auto &b:B)b=min(b,x^b);
    if(x)B.push_back(x);
}
void solve(){
    int n;cin>>n;
    vector<int>p;
    for(int i=1;i<=70;i++){
        if(miller_rabbin(i))p.push_back(i);
    }
     for(int i=1;i<=n;i++){
         int c;cin>>c;
         ll res=0ll;
         for(auto j:p){
            res<<=1;
             int cnt=0;
             while(c%j==0){
                 c/=j;cnt^=1;
             }
            res+=(ll)cnt;
         }
         insert(res);
     }
     cout<<binpow(2ll,(ll)(n-(ll)B.size()),mod)-1ll;