CF895C: Square Subsets && 【BZOJ2844】albus就是要第一个出场
这两道题很类似，都是线性基的计数问题，解题的核心思想也一样。
CF895C Square Subsets
题意
给定\(n\)个数，求多少种选数方案使得选出来的数乘积为完全平方数。\(n\leq 100000,a_i\leq70\)。
完全平方数的本质就是每个质因子的次数为偶数。
所以我们将每一个数唯一分解，然后记录每个质因子的奇偶状态，就得到了一个个01串。问题就变成了有多少个集合中的数异或为0。
我们建好线性基，设线性基的秩为\(m\)，则答案就是\(2^{n-m}-1\)。再判线性基能否组成0，如果能，答案再\(+1\)
因为线性基中的\(m\)个元素是线性无关的，并且可以表达出其他数的所有线性组合，所以其他\(2^{n-m}-1\)(减掉都不选的一种情况)的所有数都能在线性基中找到唯一的一个组合与之异或起来为0。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll p[50],cnt;
bool Insert(ll x) {
for(int i=20;i>=0;i--) {
if(!(x>>i)&1) continue ;
if(!p[i]) return p[i]=x,1;
x^=p[i];
}
return 0;
}
ll pri[100];
bool vis[100];
void pre() {
for(int i=2;i<=70;i++) {
if(!vis[i]) pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<=70;j++) {
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
void break_down(ll v) {
ll x=0;
for(int i=1;i<=pri[0];i++) {
while(v%pri[i]==0) {
x^=1<<i;
v/=pri[i];
}
}
if(!Insert(x)) cnt++;
}
int main() {
pre();
scanf("%d",&n);
ll a;
for(int i=1;i<=n;i++) {
scanf("%lld",&a);
break_down(a);
}
ll t=2,ans=1;
for(;cnt;cnt>>=1,t=t*t%1000000007) {
if(cnt&1)ans=ans*t%1000000007;
}
cout<<(ans-1+1000000007)%1000000007;
return 0;
}
【BZOJ2844】albus就是要第一个出场
我们就是要求比\(Q\)小的集合有多少个。
和上一道题一样，我们就是要求比\(Q\)小，且能被线性基表示出来的数有多少个，我们设为\(lower\)，则答案为\(lower\cdot 2^{n-m}+1\)。
问题其实就是求\(\leq Q-1\)的的最大的数的\(Rank\)。
我的实现方式不太一样。我们就找\(\leq Q-1\)的数的数量。\(\leq Q-1\)一定是从高到低的前\(i-1\)位相同，第\(i\)位小一些，后面的几位随便。于是我们就考虑\(Q\)的前\(i\)位，我们设为\(Q'\)，然后将所有数的前\(i\)位建线性基。问题就变成求有多少种方法能组合出\(Q'\)。
这样做复杂度要比网上的一般写法多一个\(log\)，不过个人感觉好理解些。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 100005
#define mod 10086
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n;
int p[35],a[N];
int Q;
bool Insert(int a) {
for(int i=30;i>=0;i--) {
if(a&(1<<i)) {
if(!p[i]) return p[i]=a,1;
else a^=p[i];
}
}
return 0;
}
int cnt;
void build(int k) {
cnt=0;
memset(p,0,sizeof(p));
for(int i=1;i<=n;i++) {
cnt+=Insert(a[i]>>k);
}
}
ll ans;
ll pw[N];
int main() {
n=Get();
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=(pw[i-1]<<1)%mod;
for(int i=1;i<=n;i++) a[i]=Get();
Q=Get();
for(int i=30;i>=0;i--) {
if(Q&(1<<i)) {
build(i);
if(!Insert((Q>>i)^1)) {
(ans+=pw[n-cnt])%=mod;
}
}
}
cout<<(ans+1)%mod;
return 0;
}