文章目录题意题解代码题意求前缀子集的子集中乘积为完全平方数的子集数量。题解乘积为完全平方数可以转换为其每一个质因子的数量都是偶数;a i a_iai​最多有一个大于1000 10001000的质因子;1000 10001000以内的质数只有168 168168个。用状态压缩表示a i a_iai​中1000 10001000以内的质数是否是奇数个1000 10001000以外的则单独储存。那么问题可以转化为子集的异或和是否为0 00。用线性基可以解决小质数的部分大质数可以看成新的一维线性基。对于一个集合方案数为2 n − r 2^{n - r}2n−rn nn为集合的元素数量r rr为秩也就是线性基的数量。2 n − r 2^{n - r}2n−r我们在集合中选择的元素可以分成线性基和非线性基两部分对于非线性基的部分无论我们如何选择线性基都会有唯一的选择。所以对于非线性基的部分每个元素都有选和不选两种。代码#includebits/stdc.husingnamespacestd;#defineendl\n#defineintlonglongusingPIIpairint,int;usingPBIpairbitset170,int;constintN5e510,M1e610,inf1e9,mod998244353;intn;intsum[N],dp[N];PBI b[N];bitset170a[N];//线性基intfa[200];//不同位的线性基的下标intr;vectorintpri;intpm[M];inttot;boolfbig[M];//大质数是否出现过bitset170fun[M];//大质数所对应的小质数的状态intksm(inta,intb){intres1;while(b){if(b%2){res(res*a)%mod;b--;}else{b1;a(a*a)%mod;}}returnres;}//线性基voidg2(bitset170x){for(inti170-1;i0;i--){if(x[i]0)continue;if(fa[i]){x^a[fa[i]];}else{fa[i]r1;a[r1]x;r;break;}}}//根据大质数的状态选择处理方式voidcho(PBI x){bitset170smallx.first;intbigx.second;if(big-1)//没有大质数{g2(small);return;}if(fbig[big])//该大质数出现过{small^fun[big];//大质数部分抵消小质数部分异或g2(small);return;}else//该大质数没出现过{fbig[big]true;fun[big]small;r;//新增一维线性基}}voidspf(intx){for(inti2;ix;i){if(!pm[i]){pm[i]i;pri.push_back(i);tot;}for(autoit:pri){intmidit*i;if(midx)break;if(pm[mid])continue;pm[mid]it;}}}PBIg(intx){bitset170res;intbig-1;for(inti0;itot;i){intcnt0;while(x%pri[i]0){x/pri[i];cnt;}if(cnt%2)//只要奇数个数的质数{res[i]1;}}if(x1000){bigx;}return{res,big};}voidsolve(){cinn;spf(1000);for(inti1;in;i){cinsum[i];b[i]g(sum[i]);}for(inti1;in;i){cho(b[i]);dp[i]ksm(2,i-r);}for(inti1;in;i){coutdp[i]endl;}}signedmain(){intT1;// cin T;while(T--){solve();}return0;}