UVA11542 题解（异或方程组的高斯消元）

· · 题解

题意

对于 n 个数，求选择若干个数字使得其乘机为完全平方数的方案数。

分析

对于完全平方数，可以分解为 x = \displaystyle\prod_{i = 1}^{k}{{p_i}^{r_i}}，其中 p_i 为质数且 r_i \equiv 0(\operatorname{mod} 2)。

结合题目每个数的最大质因子不超过 500 的条件，而 打表发现，500 以内的质数只有 95 个，所以可以把每个数分解质因数。

我们令 a_{i,j} 表示第 j 个数对应的第 j 质数的指数对二取模的值，如果该质数不是它的因子，则 a_{i,j} = 0。

则可以对每一个质数列出一个方程：

\begin{cases} a_{1,1}x_1 \otimes a_{1,2}x_2 \otimes \dots \otimes a_{1,n}x_n = 0\\ a_{2,1}x_1 \otimes a_{2,2}x_2 \otimes \dots \otimes a_{2,n}x_n = 0\\ \vdots \\ a_{m,1}x_1 \otimes a_{m,2}x_2 \otimes \dots \otimes a_{m,n}x_n = 0 \end{cases}

其中 x_i 表示是否选择第 i 个数。

然后就可以进行异或方程组的高斯消元了。

特别地，由于方程的个数可能小于未知数的个数，所以该方程不一定有唯一解，但我们其实要记录自由元的数量，即消不掉的未知数的数量。如果不是无解的情况，那答案就是 2^p-1，其中 p 是自由元的数量。

减一是因为显然所有 x 均取 0 也是一组合法解，但不能都不取，不符合题意。

而无解的情况当且仅当系数全零行最后的值为 1。

使用 bitset 优化，时间复杂度为 O(t\frac{n^2m}{w})，其中 w = 64，m 是质数的个数，也是方程的个数。这个复杂度可以通过此题。

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(register T &x)
{
    register T p = 1;
    x = 0;
    char c = getchar();
    while(c < '0'||c > '9')
    {
        if(c == '-') p = -p;
        c = getchar();
    }
    while('0' <= c&&c <= '9')
    {
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    x *= p;
}
template<typename T>inline void write(register T x)
{
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) write(x/10);
    putchar(x%10+48);
}
#define D(i,a,b) for(register int i=a;i>=b;--i)
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define N 110
const int p[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499};
const int len = 95;
int t,n,m = 100;
bitset<N> a[N];
int main()
{
    read(t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        read(n);
        F(i,1,n)
        {
            ll x;
            read(x);
            F(j,1,len)
            {
                if(x == 1) break;
                while(x % p[j] == 0)
                {
                    a[j][i] = a[j][i] ^ 1;
                    x /= p[j];  
                }   
            }
        }
        int now = 1;
        F(i,1,n)
        {
            int p = 0;
            F(j,now,m)
                if(a[j][i])
                {
                    p = j;
                    break;
                }
            if(!p) continue;
            swap(a[now],a[p]);
            F(j,1,m)
            {
                if(j == now||!a[j][i]) continue;
                a[j] ^= a[now];
            }
            ++now;
        }
        bool flag = 0;
        F(i,now,m)
            if(a[i][n+1])
            {
                flag = 1;
                break;
            }
        if(flag) puts("0");
        else write((1ll<<(n-now+1))-1),putchar('\n');
    }
    return 0;
}