HDU_5833_高斯消元

参考自：http://www.cnblogs.com/flipped/p/5771492.html

自己做的时候不知道如何求种数。看了题解，感觉思路灰常巧妙。同时也感觉这是一道好题。

精髓在于转化为线性方程组。

求素数的思想，和高斯消元需要多加熟悉。

300个最大质因数小于2000的数，选若干个它们的乘积为完全平方数有多少种方案。

合法方案的每个数的质因数的个数的奇偶值异或起来为0。

比如12=2^2*3，对应的奇偶值为01（2的个数是偶数为0，3的个数是奇数为1），3的对应奇偶值为01，于是12*3是完全平方数。

然后异或方程组就是：

a₁₁x₁+a₁₂x₂+...+a_1nx_n=0

a₂₁x₁+a₂₂x₂+...+a_2nx_n=0

...

a_n1x₁+a_n2x₂+...+a_nnx_n=0

a_ij：第i个质数（2000内有303个质数）在第j个数里是奇数个则为1，否则为0。

x_i：第i个数（最多300个数）被选则为1，否则为0。

求出有多少种解即可。（异或方程组高斯消元求秩，然后解就有2^(n-rank)种，减去全为0的解）

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

#define LL long long

#define mod 1000000007

const int N=;

const int M=;

int prime[N+],cnt;

int n,t,mat[M][M];

LL a[M];

void getPrime()   //求2000以内的所有质数

{

    for(int i=; i<=N; i++)

    {

        if(!prime[i])

            prime[++cnt]=i;

        for(int j=; j<=cnt&&prime[j]<=N/i; j++)

        {

            prime[prime[j]*i]=;

            if(i%prime[j]==)

                break;

        }

    }

}

int Rank(int c[][M])   //高斯消元求方程组的秩（线性表换将矩阵转化为上阶梯形矩阵）

{

    int i=,j=,k,r,u;

    while(i<=cnt&&j<=n)

    {

        r=i;

        while(c[r][j]==&&r<=cnt) r++;

        if(c[r][j])

        {

            swap(c[i],c[r]);

            for(u=i+; u<=cnt; u++)

                if(c[u][j])

                    for(k=i; k<=n; k++)

                        c[u][k]^=c[i][k];

            i++;

        }

        j++;

    }

    return i;

}

int solve()

{

    memset(mat,,sizeof(mat));

    for(int i=; i<=n; i++)

        for(int j=; j<=cnt; j++)

        {

            LL tmp=a[i];

            while(tmp%prime[j]==)

            {

                tmp/=prime[j];

                mat[j][i]^=;

            }

        }

    int b=n-Rank(mat);

    LL ans=,k=;

    while(b)       //快速幂

    {

        if(b&)

            ans=ans*k%mod;

        k=k*k%mod;

        b>>=;

    }

    return ans-;

}

int main()

{

    int cas=;

    getPrime();

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%I64d",&a[i]);//cout<<"*";

        printf("Case #%d:\n%d\n",cas++,solve());

    }

}

巴特西

HDU_5833_高斯消元

最新文章

热门文章