首页 > 代码库 > HDU5088

HDU5088

对于每个数,把它看做0和1组成的行,n个数就是n行,判断形成的矩阵中【秩】是否等于【n】

#include<iostream>#include<cstdio>using namespace std;const int NO=1005;long long s[65][NO];long long p[NO];int GET(long long k){    int ans=0;    while(k)    {        k>>=1;        ans++;    }    return ans;}int main(){    freopen("1.txt","r",stdin);    int ttt,n;    scanf("%d",&ttt);    while(ttt--)    {        for(int i=0;i<=64;i++)            s[i][0]=0;        scanf("%d",&n);        for(int i=1;i<=n;i++)        {            scanf("%I64d",&p[i]);            int kkk=GET(p[i]&-p[i]);            s[kkk][++s[kkk][0]]=p[i];        }        if(n>40)        {            puts("Yes");            continue;        }        int num=0;        for(int i=1;i<=64;i++)            if(s[i][0])            {                for(int j=2;j<=s[i][0];j++)                {                    long long k=s[i][1]^s[i][j];                    int kkk=GET(k&-k);                    s[kkk][++s[kkk][0]]=k;                }                num++;            }        puts(num==n?"No":"Yes");    }    return 0;}
View Code

 

HDU5088