CF895C Square Subsets(状压+二项式定理优化)

传送门

由于完全平方数,是质因子分解后,每个质因子的质数都为偶数的数

70 70 70以内只有 19 19 19个质因子,所以可以状压每个质因子的奇偶性质

f [ i ] [ j ] f[i][j] f[i][j]表示考虑完第 i i i个数目前质因子奇偶性为 j j j的方案数

然后暴力一点,枚举每个数,有转移方程,其中 w w w是当前数字的状态

f [ i ] [ j ⊕ w ] = f [ i − 1 ] [ j ] f[i][j\oplus w]=f[i-1][j] f[i][jw]=f[i1][j]

第一维可以滚动掉,但是复杂度仍然是 O ( n 2 ) O(n^2) O(n2)

发现相同的数字要么选奇数个,要么选偶数个

设数字 w w w x x x

选奇数个的方案数是 C x 1 + C x 3 . . . . . C_x^1+C_x^3..... Cx1+Cx3.....

选偶数个的方案数是 C x 2 + C x 4 . . . . . . . C_x^2+C_x^4....... Cx2+Cx4.......

直接计算的复杂度还是很大,但是这个可以用二项式定理来优化

( 1 + 1 ) x = ∑ i = 0 x C x i (1+1)^x=\sum\limits_{i=0}^xC_x^i (1+1)x=i=0xCxi

( 1 − 1 ) x = ∑ i = 0 x ( − 1 ) i C x i (1-1)^x=\sum\limits_{i=0}^x(-1)^iC_x^i (11)x=i=0x(1)iCxi

那么 ( 1 + 1 ) x + ( 1 − 1 ) x = 2 ∗ ∑ i ∣ 2 C x i (1+1)^x+(1-1)^x=2*\sum\limits_{i|2}C_x^i (1+1)x+(11)x=2i2Cxi

这就是选偶数个的方案数

那么选奇数个的方案数就是拿 2 x 2^x 2x减去上面的方案即可

#include bits/stdc++.h
using namespace std;
#define int long long
const int mod = 1e9+7;
int zhi[21] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int state[72],f[119],vis[72],n,g[119],mx = 119;
int quick(int x,int n)
{
	int ans = 1;
	for( ; n ; n=1,x=x*x%mod )
		if( n1 )	ans = ans*x%mod;
	return ans;
}
signed main()
{
	for(int i=2;i=70;i++)
	{
		int x = i;
		for(int j=0;j=18;j++)
		{
			int temp = 0;
			while( x%zhi[j]==0 )	x/=zhi[j],state[i] ^= (1j);
		}
	}
	cin  n; f[0] = 1;
	for(int i=1;i=n;i++){ int w; scanf("%lld",w); vis[w]++; }
	for(int i=2;i=70;i++)
	{
		if( vis[i]==0 )	continue;
		int ou = quick(2,vis[i]-1);//不需要减1,因为不选也是一种选法 
		int ji = quick(2,vis[i] )-ou;
		for(int j=0;jmx;j++)
		{
			g[j] = ( g[j]+f[j]*ou%mod )%mod;
			g[j^state[i]] = ( g[j^state[i]] + f[j]*ji%mod )%mod;
		}
		for(int j=0;jmx;j++)	f[j] = g[j],g[j] = 0;
	}
	f[0] = quick(2,vis[1] )*f[0]%mod-1;//减去1,因为包含一个都不选的方案数
	cout  (f[0]+mod)%mod;
}
最新回复(0)
/jishurdnjMIpJZidQ2sQV2FCqAkzXYNAH_2FU1PRS7T5E8vaJo_3D4834422
8 简首页