CodeforcesRound#448(Div.2)C.SquareSubsets乘积为平方数的集合个数状压dpOR线性基

题目链接&＃xff1a;https://codeforces.com/contest/895/problem/C
题目大意&＃xff1a;给你n个数。问有多少个子集的乘积为平方数。mod &＃xff08;1e9&＃43;7&＃xff09;。

思路一&＃xff1a;
如果一个数的质因数都为偶数个&＃xff0c;那么这个数就是平方数。
因为a[i]<&＃61;70。我们用状压来表示每个数的质因数的奇偶状态。奇为1.偶为0。

我们用dp[i][s]表示前i个数组成乘积为状态s的方案数。
然后我们枚举i-1的状态s转移。

如果i选择偶数个,那么i自己的集合为0&＃xff0c; 那么i-1的状态必须为s。

如果i选择奇数个&＃xff0c;那么i自己的集合为s0^s&＃xff0c; 那么i-1的状态为s。

然后用滚动数组。

思路二&＃xff1a;

法一&＃xff1a;
#include
#define LL long long
using namespace std;LL a[100005];
LL cut[75];
const LL p[]&＃61;{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};//19
LL c2[100005]&＃61;{1};
LL f[2][1<<21];const int mod &＃61; 1e9&＃43;7;
int main()
{int n;scanf("%d", &n);for(LL i&＃61;1; i<&＃61;n; i&＃43;&＃43;){scanf("%lld", &a[i]);cut[a[i]]&＃43;&＃43;;}for(LL i&＃61;1; i<&＃61;n; i&＃43;&＃43;){c2[i]&＃61;c2[i-1]*2%mod;}f[0][0]&＃61;1;//初始化int I&＃61;0;for(LL i&＃61;1; i<&＃61;70; i&＃43;&＃43;){if(cut[i]&＃61;&＃61;0){continue;}I^&＃61;1;int s0&＃61;0;//i本身的状态int SI&＃61;i;for(int k&＃61;0; k<19; k&＃43;&＃43;){while(SI%p[k]&＃61;&＃61;0){s0^&＃61;(1<<k);SI/&＃61;p[k];}}memset(f[I], 0, sizeof(f[I]));for(LL s&＃61;0; s<(1<<19); s&＃43;&＃43;){//枚举i-1的状态sf[I][s]&＃43;&＃61;f[I^1][s]*c2[cut[i]-1]%mod;//如果i选择偶数个新状态为0^sf[I][s^s0]&＃43;&＃61;f[I^1][s]*c2[cut[i]-1]%mod;//如果i选择奇数个新状态为s^s0}}printf("%lld\n", (f[I][0]-1&＃43;mod)%mod);//f[0][0]为空集。不满足-1return 0;
}发二&＃xff1a;
#include
#define reg register
#define LL long long
using namespace std;
typedef long long ll;
const int MN&＃61;60;
ll a[61],tmp[61];
const LL p[]&＃61;{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};//19
LL c2[100005]&＃61;{1};
const int mod &＃61; 1e9&＃43;7;bool flag;
void ins(ll x){//构造for(reg int i&＃61;MN;~i;i--)if(x&(1ll<<i))if(!a[i]){a[i]&＃61;x;return;}else x^&＃61;a[i];flag&＃61;true;
}bool check(ll x){//是否能够插入 判断是否能够异或出一个数for(reg int i&＃61;MN;~i;i--)if(x&(1ll<<i))if(!a[i])return false;else x^&＃61;a[i];return true;
}ll qmax(ll res&＃61;0){//最大值for(reg int i&＃61;MN;~i;i--)res&＃61;max(res,res^a[i]);return res;
}ll qmin(){//最小值if(flag)return 0;for(reg int i&＃61;0;i<&＃61;MN;i&＃43;&＃43;)if(a[i])return a[i];
}ll query(ll k){//第k小reg ll res&＃61;0;reg int cnt&＃61;0;k-&＃61;flag;if(!k)return 0;for(reg int i&＃61;0;i<&＃61;MN;i&＃43;&＃43;){for(int j&＃61;i-1;~j;j--)if(a[i]&(1ll<<j))a[i]^&＃61;a[j];if(a[i])tmp[cnt&＃43;&＃43;]&＃61;a[i];}if(k>&＃61;(1ll<<cnt))return -1;for(reg int i&＃61;0;i<cnt;i&＃43;&＃43;)if(k&(1ll<<i))res^&＃61;tmp[i];return res;
}int getnum(int x){int ans&＃61;0;for(int k&＃61;0; k<19; k&＃43;&＃43;){while(x%p[k]&＃61;&＃61;0){ans^&＃61;(1<<k);x/&＃61;p[k];}}return ans;
}int main(){int n, x;scanf("%d",&n);for(LL i&＃61;1; i<&＃61;n; i&＃43;&＃43;){c2[i]&＃61;c2[i-1]*2%mod;}for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){scanf("%d", &x);ins(getnum(x));}for(reg int i&＃61;MN;~i;i--){if(a[i]){n--;}}printf("%lld\n",c2[n]-1);return 0;
}