题目描述

难度分:$2000$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 70)$。
输出有多少个非空子序列，其元素乘积是完全平方数。模$10^9+7$。

注：子序列不一定连续。
注：只要有元素下标不一样，就算做不同的子序列。

输入样例$1$

4
1 1 1 1

输出样例$1$

15

输入样例$2$

4
2 2 2 2

输出样例$2$

7

输入样例$3$

5
1 2 4 5 8

输出样例$3$

7

算法

状压DP

将一个数分解质因数，如果它是平方数则要求每个质因子的个数都是偶数。而题目中$a[i]$的取值范围很小，经过枚举，发现$[1,70]$中的质数只有$19$个，因此可以用一个$19$位二进制数$mask$来表征某个数分解质因数后的状态，如果第$i$位（从$0$开始）为$1$，说明这个数分解质因数后，第$i$个质数有奇数个，否则就是偶数个。看到奇偶性，就能比较容易地想到要用异或的性质。

先遍历$a$数组，预处理出每个$a[i]$的频数，存入到数组$cnt$中，$cnt[i]$表示数组$a$中$i$的个数。

状态定义

$dp[i][mask]$表示考虑从数值$[1,i]$取数，且这些数的乘积状态为$mask$的情况下，一共有多少种非空子序列。在这个定义下，最终答案就应该是$dp[70][0]-1$（减去的$1$是空序列）。

状态转移

当考虑到数值$i$时，分为以下两种情况：

1. 如果$cnt[i]=0$，直接状态转移$dp[i][mask]=dp[i-1][mask]$，$mask \in [0,2^{19})$。
2. 否则当前数值$i$可以从$a$中取奇数个和偶数个，假设$i$分解质因数后的状态为$cur$，选奇数个$i$，由于奇数个$i$的乘积状态和一个$i$的乘积状态相同，所以对于$mask \in [0,2^{19})$，状态转移方程为$dp[i][mask \oplus cur]=dp[i][mask \oplus cur] + dp[i-1][mask] \times 2^{cnt[i]-1}$。选偶数个$i$相当于没有选$i$，所以状态转移方程为$dp[i][mask]=dp[i][mask] + dp[i-1][mask] \times 2^{cnt[i]-1}$。

这里面用到的是二项式定理，$C_{k}^{1}+C_{k}^{3}+C_{k}^{5}+…=C_{k}^{2}+C_{k}^{4}+C_{k}^{6}+…=2^{k-1}$。

最后需要注意的是空间可能会爆，可以开$2 \times 2^{19}$的DP数组进行滚动。

复杂度分析

时间复杂度

这个题的时间复杂度跟$n$没有什么关系，主要在于$a[i]$的范围。外层循环遍历$i \in [1,70]$，对每个$i$循环$19$次求质因数分解的状态，然后遍历状态$mask \in [0,2^{19})$进行转移，单次转移是$O(1)$的。因此，算法整体的常数操作不到$4 \times 10^7$，可以极限通过。

空间复杂度

我在实现的时候开辟了一个$O(n)$的空间存$p[i]=2^i$，事实上这个空间可以省去，只留下$2 \times 2^{19}=2^{20}$规模的DP数组。而$cnt$数组的空间可以忽略不计，因此本算法的额外空间为$2^{20}$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010, MOD = 1e9 + 7;
const int primes[19] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};
int n, a, cnt[71], p[N];
LL dp[2][1<<19];

int main() {
    scanf("%d", &n);
    memset(cnt, 0, sizeof(cnt));
    p[0] = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = (p[i - 1] << 1) % MOD;
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a);
        cnt[a]++;
    }
    dp[0][0] = 1;
    int index = 0;
    for(int i = 1; i <= 70; i++) {
        if(cnt[i] == 0) continue;
        int k = cnt[i], x = i, cur = 0;
        index ^= 1;
        for(int j = 0; j < 19 && primes[j] <= x; j++) {
            while(x % primes[j] == 0) {
                cur ^= 1<<j;
                x /= primes[j];
            }
        }
        memset(dp[index], 0, sizeof(dp[index]));
        for(int mask = 0; mask < (1<<19); mask++) {
            dp[index][mask^cur] = (dp[index][mask^cur] + dp[index^1][mask] * p[k - 1] % MOD) % MOD;
            dp[index][mask] = (dp[index][mask] + dp[index^1][mask] * p[k - 1] % MOD) % MOD;
        }
    }
    printf("%d\n", (dp[index][0] - 1 + MOD) % MOD);     // 注意还要减去一个空序列
    return 0;
}