@Junlier
2018-08-19T22:25:20.000000Z
字数 2239
阅读 1652
数学方法——线性基
先膜一下mona,感谢他生动的讲解……Orz
然后
这哥们讲的不错
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 55
using namespace std;
const int Inf=1e9;
int n;
lst p[N];
il lst read()
{
rg lst s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
il void Insert(rg lst x)
{
for(rg int i=50;i>=0;--i)
{
if(!(x&(1ll<<i)))continue;
if(!p[i])p[i]=x;
x^=p[i];
}
}
il lst Query(rg lst x)
{
for(rg int i=50;i>=0;--i)
x=max(x,x^p[i]);
return x;
}
int main()
{
n=read();
for(rg int i=1;i<=n;++i)
Insert(read());
printf("%lld\n",Query(0));
return 0;
}
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 55
#define mod 2008
using namespace std;
const int Inf=1e9;
int n,m,ans;
lst p[N];
char light[N];
il int read()
{
rg int s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
il void Insert(rg lst x)
{
for(rg int i=50;i>=0;--i)
{
if(!(x&(1ll<<i)))continue;
if(!p[i])p[i]=x;
x^=p[i];
}
}
il lst qpow(rg int a,rg int b)
{
rg lst base=a,res=1;
while(b)
{
if(b&1)res=(res*base)%mod;
base=(base*base)%mod;
b>>=1;
}
return res;
}
int main()
{
n=read(),m=read();
for(rg int i=1;i<=m;++i)
{
scanf("%s",light);
rg lst ss=0;
for(rg int j=0;j<n;++j)
ss=ss*2+(light[j]=='O'?1:0);
Insert(ss);
}
for(rg int i=50;i>=0;--i)
if(p[i])ans++;
printf("%lld\n",qpow(2,ans));
return 0;
}