洛谷CF895C Square Subsets（线性基）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

洛谷传送门

不知道线性基是什么东西的可以看看蒟蒻的总结

题意：

给你n个数，每个数<=70，问有多少个集合，满足集合中所有数相乘是个完全平方数（空集除外）

题解：

完全看不出这玩意儿和线性基有什么关系……我可能太菜了……

首先，一个完全平方数分解质因数之后每个质因子都出现偶数次

又因为小于等于$70$的质数总共18个，可以用18位的二进制表示，0表示偶数次，1表示奇数次

那么两个数相乘就是每一个质因子表示的位的异或

那么就是求有多少种方法相乘得0

首先求出原数组的线性基，设$cnt$表示线性基内数的个数

那么答案就是$2^{n-cnt}-1$

证明：线性基内的数是最小线性无关组

那么除了线性基内的所有数的子集都能被线性基内的数张成（就是表示出来）

那么上面的所有子集和张成相等，两者异或起来为0

所以把线性基内的数除去，剩下的数的所有子集都能与线性基内的数异或成0

那么答案就是真子集个数

//minamoto
#include<iostream>
#include<cstdio>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=1e5+,M=,mod=1e9+;
int p[]={,,,,,,,,,,,,,,,,,,};
int b[M],a[N],n,cnt;
inline int ksm(int x,int y){
int res=;
while(y){
if(y&) res=1ll*res*x%mod;
x=1ll*x*x%mod,y>>=;
}
return res;
}
void insert(int x){
for(int i=;i>=;--i){
if(x>>i&){
if(!b[i]){b[i]=x;break;}
x^=b[i];
}
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
for(int i=;i<=n;++i){
int x=read();
for(int j=;j<=;++j){
if(x%p[j]==){
int now=;
while(x%p[j]==) x/=p[j],now^=;
a[i]|=now<<j;
}
}
}
for(int i=;i<=n;++i) insert(a[i]);
for(int i=;i<=;++i)
if(b[i]) --n;
printf("%d\n",ksm(,n)-);
return ;
}