专栏首页饶文津的专栏【HDU 5833】Zhu and 772002(异或方程组高斯消元)

【HDU 5833】Zhu and 772002(异或方程组高斯消元)

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

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

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

然后异或方程组就是:

a11x1+a12x2+...+a1nxn=0

a21x1+a22x2+...+a2nxn=0

...

an1x1+an2x2+...+annxn=0

aij:第i个质数(2000内有303个质数)在第j个数里是奇数个则为1,否则为0。

xi:第i个数(最多300个数)被选则为1,否则为0。

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

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
#define mod 1000000007
using namespace std;
const int N=2000;
const int M=310;
int prime[N+1],cnt;
int n,t,mat[M][M],two[M]={1};
ll a[M];
void getPrime(){
    for(int i=2;i<=N;i++){
        if(!prime[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]<=N/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int Rank(int c[][M]){//异或版的高斯消元求秩
    int i=0,j=0,k,r,u;
    while(i<=cnt&&j<=n){
        r=i;
        while(c[r][j]==0&&r<=cnt)r++;
        if(c[r][j]){
            swap(c[i],c[r]);
            for(u=i+1;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,0,sizeof mat);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=cnt;j++){
            ll tmp=a[i];
            while(tmp%prime[j]==0){
                tmp/=prime[j];
                mat[j][i]^=1;
            }
        }
    int b=n-Rank(mat);//b个自由元
    return two[b]-1;//减去全为0的解
}
int main() {
    getPrime();
    for(int i=1;i<M;i++)two[i]=two[i-1]*2%mod;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        printf("Case #%d:\n%d\n",cas,solve());
    }
    return 0;
}

  原来是白书上的题(160页)I good vagetable a!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「CodeForces - 598B」Queries on a String

    字符串s(1 ≤ |s| ≤ 10 000),有m(1 ≤ m ≤ 300)次操作,每次给l,r,k,代表将r位置插入l位置前,执行k(1 ≤ k ≤ 1 00...

    饶文津
  • 【BZOJ 1701】Cow School(斜率优化/动态凸包/分治优化)

    小牛参加了n个测试,第i个测试满分是??pi,它的得分是??ti。老师去掉??/??ti/pi最小的d个测试,将剩下的总得分/总满分作为小牛的得分。小牛想知道多...

    饶文津
  • 「2017 Multi-University Training Contest 1」2017多校训练1

    饶文津
  • [算法] 数组排序 - 冒泡排序法与直接选择排序法

    两种算法都很基础,但是思考的方向还是有着些许差异的。 另外想要更快的去解决排序问题的话,可以下功夫去研究一下库里面的 qsort函数,也非常的实用!

    泰坦HW
  • 洛谷P3245 [HNOI2016]大数(莫队)

    两个位置\(l, r\)满足条件当且仅当\(S_l - S_r = 0\),也就是\(S_l = S_r\)

    attack
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • ECJTUACM16 Winter vacation training #4 题解&源码

    https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

    Angel_Kitty
  • 排序算法之我观

    笔者今年是xmu大一新生 9月初学编程 学到泡排的时候就对排序这一块深入了解 (也只是很粗浅地学习了一下) 写这篇文章的初衷就是复习一下之前所学,有不足...

    glm233
  • 数据结构与算法(二)——十大排序算法

      秋招已经开启一个月了,九月份和十月份是我们秋招找工作的黄金时期。但是大多数的企业都会在笔试或者面试中会考察我们数据结构的知识点,有的会直接考查数据结构的代码...

    stefan666
  • 算法练习(4)-数组去重合并

    这是日常工程中,经常会遇到的场景,拿到2个list,里面有重复元素,要求去重合并最终排序输出。

    菩提树下的杨过

扫码关注云+社区

领取腾讯云代金券