传送门
由于完全平方数,是质因子分解后,每个质因子的质数都为偶数的数
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][j⊕w]=f[i−1][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=0∑xCxi
(
1
−
1
)
x
=
∑
i
=
0
x
(
−
1
)
i
C
x
i
(1-1)^x=\sum\limits_{i=0}^x(-1)^iC_x^i
(1−1)x=i=0∑x(−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+(1−1)x=2∗i∣2∑Cxi
这就是选偶数个的方案数
那么选奇数个的方案数就是拿
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);
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;
cout (f[0]+mod)%mod;
}
