[关闭]
@Junlier 2018-08-19T22:25:20.000000Z 字数 2239 阅读 1639

线性基学习

数学方法——线性基
先膜一下mona，感谢他生动的讲解……Orz
然后
这哥们讲的不错

我的板子

第一个

luoguP3812模板

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 55
  17. using namespace std;
  18. const int Inf=1e9;
  20. int n;
  21. lst p[N];
  23. il lst read()
  24. {
  25.     rg lst s=0,m=0;rg char ch=getchar();
  26.     while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  27.     while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  28.     return m?-s:s;
  29. }
  31. il void Insert(rg lst x)
  32. {
  33.     for(rg int i=50;i>=0;--i)
  34.     {
  35.         if(!(x&(1ll<<i)))continue;
  36.         if(!p[i])p[i]=x;
  37.         x^=p[i];
  38.     }
  39. }
  41. il lst Query(rg lst x)
  42. {
  43.     for(rg int i=50;i>=0;--i)
  44.         x=max(x,x^p[i]);
  45.     return x;
  46. }
  48. int main()
  49. {
  50.     n=read();
  51.     for(rg int i=1;i<=n;++i)
  52.         Insert(read());
  53.     printf("%lld\n",Query(0));
  54.     return 0;
  55. }

第二个……

luogu彩灯

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 55
  17. #define mod 2008
  18. using namespace std;
  19. const int Inf=1e9;
  21. int n,m,ans;
  22. lst p[N];
  23. char light[N];
  25. il int read()
  26. {
  27.     rg int s=0,m=0;rg char ch=getchar();
  28.     while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  29.     while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  30.     return m?-s:s;
  31. }
  33. il void Insert(rg lst x)
  34. {
  35.     for(rg int i=50;i>=0;--i)
  36.     {
  37.         if(!(x&(1ll<<i)))continue;
  38.         if(!p[i])p[i]=x;
  39.         x^=p[i];
  40.     }
  41. }
  43. il lst qpow(rg int a,rg int b)
  44. {
  45.     rg lst base=a,res=1;
  46.     while(b)
  47.     {
  48.         if(b&1)res=(res*base)%mod;
  49.         base=(base*base)%mod;
  50.         b>>=1;
  51.     }
  52.     return res;
  53. }
  55. int main()
  56. {
  57.     n=read(),m=read();
  58.     for(rg int i=1;i<=m;++i)
  59.     {
  60.         scanf("%s",light);
  61.         rg lst ss=0;
  62.         for(rg int j=0;j<n;++j)
  63.             ss=ss*2+(light[j]=='O'?1:0);
  64.         Insert(ss);
  65.     }
  66.     for(rg int i=50;i>=0;--i)
  67.         if(p[i])ans++;
  68.     printf("%lld\n",qpow(2,ans));
  69.     return 0;
  70. }

题单(没错，xzy的)

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注