本文主要是介绍codeforces 895C Square Subsets，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定n个数，要求选出一个非空子集使得其乘积为某个数的平方，求方案数。
因为某个数的完全平方数其质因子肯定都为偶数次幂，反之，质因子全为偶数次幂的数是一个完全平方数，由于每一个数字都小于等于70，最多只有19个质因数，所以我们可以对每个质因子进行状压，用dp[i][state]表示考虑到第i个数字，当前幂次方的奇偶性为state的方案数。
我们可以先通过预处理出每个数字对于每个质因子是奇数次幂还是偶数次幂，为can[i]，因为两数相乘就相当于幂次方相加，接着枚举每一个数字，设当前枚举到的状态为state，那么如果当前数字选了奇数个，那么下一步的状态就是state^can[i]，可转移到这一步的状态有c(i,1)+c(i,3)+...+c(i,cnt[i]/2)，为2的(cnt[i]-1)次方，如果当前数字选了偶数个，那么下一步的状态就是state不变，因为i的每个质因子都是偶数次幂了，转移的方案数同理也是为2的(cnt[i]-1)次方。
最后答案就是dp[70][0]了，由于要求非空还要将答案-1。
下附AC代码。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 75
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n;
int a[maxn];
int mypow[100005];
int dp[71][(1<<19)];
int can[maxn],cnt[maxn];
int pri[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int main()
{for(int i=1;i<=70;i++){for(int j=0;j<19;j++){if(i%pri[j]==0){int x=i;while(x%pri[j]==0){can[i]^=(1<<j);x/=pri[j];}}}}mypow[0]=1;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);cnt[x]++;mypow[i]=(mypow[i-1]*2)%mod;}dp[0][0]=1;for(int i=1;i<=70;i++){if(!cnt[i]){for(int j=0;j<(1<<19);j++)dp[i][j]=dp[i-1][j];}else{for(int state=0;state<(1<<19);state++)if(dp[i-1][state]){ll temp=((long long)dp[i][state]+((long long)dp[i-1][state]*mypow[cnt[i]-1]));temp%=mod; dp[i][state]=temp;temp=(long long)dp[i][state^can[i]]+((long long)dp[i-1][state]*mypow[cnt[i]-1]);temp%=mod;dp[i][state^ can[i]]=temp;}}}printf("%I64d\n",(dp[70][0]-1+mod)%mod);
}这篇关于codeforces 895C Square Subsets的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
