Codeforces Round #448 (Div. 2):C题Square Subsets——线性基|状压dp

题目链接:https://codeforces.com/contest/895/problem/C

 题意:给你n个数,每个数<=70,问有多少个集合,满足集合中所有数相乘是个完全平方数(空集除外)

题解:比赛时对这个一点思路都没有,自闭了,但是观察到数小,考虑可以用状压dp来求,但是发现很不好想,也不好调,赛后意外发现学长写的这个题的题解,发现竟然可以用线性基来求,而且相对而言也比较好码,就是不容易想到。

首先如果一个数是完全平方数,那么根据唯一分解定理,一个完全平方数唯一分解后其质因子出现的个数为偶数。

然后基于这个事实以及数据小(小于70的质因数仅有19个)

我们考虑可以把读入的每一个数表示成一个19位的二进制数,每一位上为1表示该质因子出现次数为奇数,否则为偶数。

然后问题就变成了,给你n个数,求满足异或和为0的集合个数。

最后就是一个结论了:求出这n个数组成集合的线性基,答案就是2^(n-线性基大小)-1.

具体的证明:因为线性基里面的任意一些数异或起来不为0,所以没插入到线性基里面的数肯定可以通过异或最后变成0.

那么答案就是这些没有插入到线性基的数的集合大小。

#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#define PI atan(1.0)*4
#define E 2.718281828
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
using namespace std;
inline int read()
{
    int a=0,b=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            b=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        a=(a<<3)+(a<<1)+c-'0';
        c=getchar();
    }
    return a*b;
}
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
const int N = 1e5+7;
int a[N];
int prime[21] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int ans[21];
ll quick_mod(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=(res*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return res%mod;
}
int main(){
	int n=read();
	rp(i,1,n){
		int x=read();
		rp(j,0,18){
			int num=0;
			while(x%prime[j]==0){
				x/=prime[j];
				num^=1;
			}
			a[i]|=num*(1<<j); 
		}
	}
	rp(i,1,n){
		RP(j,18,0){
			if(a[i]&(1<<j)){
				if(ans[j]==0){
					ans[j]=a[i];
					break;
				}
				else a[i]^=ans[j];
			}
		}
	}
	ll sum=n;
	rp(i,0,18) if(ans[i]) sum--;
	printf("%lld\n",quick_mod(2ll,sum)-1);
    return 0;
}

 

Codeforces Round #448 (Div. 2):C题Square Subsets——线性基|状压dpCodeforces Round #448 (Div. 2):C题Square Subsets——线性基|状压dp 木每立兄豪 发布了315 篇原创文章 · 获赞 201 · 访问量 1万+ 私信 关注
上一篇:LeetCode 78. 子集(Subsets) 34


下一篇:JAVA解Leetcode 90题 Subsets