无平方子集计数

题意：

题目简化题意是，求有多子序列，子序列的乘积不能有超过$2$个及以上的质因子。

题意乍一读很迷惑，然后我就做了很久的假题。。
然后最后写完假做法，发现读错题了，最后假做法修修补补，变成了这个状压dp的做法。

做法一（笨蛋三进制）：

$dp$的意义是，前 $i$ 个数，状态为 $j$ 的方案数。
这个状态，是一个三进制数，表示选中的子序列，$10$ 种质因子的幂次（30以内的质因子也就 $10$ 个，所以状态的大小是 $3^{10}$），因为这个幂次 $>=2$ 的时候，就对答案无贡献了，所以只需要关注 $0,1,2$ 这三种状态即可。
这个复杂度大概是 $1000*$$3^{10}$，是一个很极限的复杂度。。
我也是各种优化，然后终于过了，最多优化到 $920ms$

做法二（聪明二进制，对上面的三进制优化了一下）

$dp$的意义不变，仍是前 $i$ 个数，状态为 $j$ 的方案数。
因为 $3$ 进制状态下的 $2$ 很 $useless$，想办法省去他，复杂度能降一个数量级。
然后发现真的能省去，只要在 $dp$ 转移的时候，忽略掉 同一个质因子幂次都 $>=1$ 的状态即可。

三进制代码：

int f[2][59049];
class Solution {
public:
    const int mod = 1e9 + 7;
    vector<int> pi = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int ying[40];
    int p[40], c[40], jiyi[40];
    int calc(int n)
    {
        if (jiyi[n]) {
            return jiyi[n];
        }
        int nn = n;
        for (int i = 1; i <= 10; i++) {
            p[i] = c[i] = 0;
        }
        int cnt = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                p[++cnt] = i;
                int sum = 0;
                while(n % i == 0) {
                    sum++;
                    n /= i;
                }
                c[cnt] = sum;
            }
        }
        if (n != 1) {
            p[++cnt] = n;
            c[cnt] = 1;
        }
        int val = 0;
        for (int j = 1; j <= cnt; j++) {
            val += ying[p[j]] * min(2, c[j]);
        }
        return jiyi[nn] = val;
    }
    int huo (int x, int y)
    {
        int ret = 0;
        int c = 1;
        for (int i = 0; i < 10; i++) {
            ret += c * min(2, x / c % 3 + y / c % 3);
            c *= 3;
        }
        return ret;
    }
    int a[1005];
    bool tong[59049];
    int squareFreeSubsets(vector<int>& nums) {
        memset(f, 0, sizeof(f));
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int len = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 4 == 0 || nums[i] % 25 == 0 || nums[i] % 9 == 0) {
                continue;
            }
            a[len++] = nums[i];
        }
        int mul = 1;
        for (int i = 0; i < 10; i++) {
            ying[pi[i]] = mul;
            mul *= 3;
        }

        for (int j = 0; j < 59049; j++) {
            int c = 1;
            bool ok = 1;
            for (int k = 0; k < 10; k++) {
                if (j / c % 3 >= 2) {
                    ok = 0;
                    break;
                }
                c *= 3;
            }
            if (!ok) continue;
            tong[j] = 1;
        }

        for (int i = 0; i < len; i++) {
            int val = calc(a[i]);
            for (int j = 0; j < 59049; j++) {
                if (f[i & 1][j] == 0 || !tong[j]) {
                    continue;
                }
                f[(i + 1) & 1][j] = f[i & 1][j];
            }
            f[(i + 1) & 1][val]++;
            for (int j = 0; j < 59049; j++) {
                if (f[i & 1][j] == 0 || !tong[j]) {
                    continue;
                }
                (f[(i + 1) & 1][huo(j, val)] += f[i & 1][j]) %= mod;
            }
            memset(f[i & 1], 0, sizeof(f[i & 1]));
        }
        int ans = 0;
        for (int j = 0; j < 59049; j++) {
            if (!tong[j]) continue;
            ans = (ans + f[len & 1][j]) % mod;
        }
        return ans;
    }
};

二进制代码：

class Solution {
public:
    const int mod = 1e9 + 7;
    vector<int> pi = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int ying[40];
    int p[40], c[40], jiyi[40];
    int a[1005];
    int f[2][1024];
    int calc(int n)
    {
        if (jiyi[n]) return jiyi[n]; 
        int nn = n;
        for (int i = 1; i <= 10; i++) p[i] = c[i] = 0; 
        int cnt = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                p[++cnt] = i;
                int sum = 0;
                while(n % i == 0) n /= i; 
                c[cnt] = sum;
            }
        }
        if (n != 1) p[++cnt] = n; 
        int val = 0;
        for (int j = 1; j <= cnt; j++) val += 1 << ying[p[j]]; 
        return jiyi[nn] = val;
    }
    int squareFreeSubsets(vector<int>& nums) {
        for (int i = 0; i < 10; i++) {
            ying[pi[i]] = i;
        }
        int n = nums.size();
        int len = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 4 == 0 || nums[i] % 25 == 0 || nums[i] % 9 == 0) continue; 
            a[len++] = nums[i];
        }

        for (int i = 0; i < len; i++) {
            int val = calc(a[i]);
            memcpy(f[(i + 1) & 1], f[i & 1], sizeof(f[i & 1]));
            f[(i + 1) & 1][val] = (f[(i + 1) & 1][val] + 1) % mod;
            for (int j = 0; j < 1024; j++) {
                if (j & val) continue; 
                f[(i + 1) & 1][j | val] = (f[(i + 1) & 1][j | val] + f[i & 1][j]) % mod;
            }
            memset(f[i & 1], 0, sizeof(f[i & 1]));
        }
        int ans = 0;
        for (int j = 0; j < 1024; j++) ans = (ans + f[len & 1][j]) % mod; 
        return ans;
    }
};

找出对应 LCP 矩阵的字符串

题意：

略 非常简单题意，建议自己看

做法：

很容易想到，只要 $lcp_{i,j}$ 不等于 $0$ ，显然此时 $ans_i = ans_j$，那么就可以并查集。
并查集结束后，再做一遍 $dp$，判断与给定的 $dp$ 数组是不是相同即可。

class Solution {
public:
    int fa[1005];
    bool vis[1005];
    int f[1005][1005];
    int getf(int x){
        if (x == fa[x]) {
            return x;
        }
        return fa[x] = getf(fa[x]);
    }
    string findTheString(vector<vector<int>>& lcp) {
        if (lcp.size() == 0) {
            return "";
        }
        int n = lcp.size();
        int m = lcp[0].size();
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
        string ans = "";
        for (int i = 0; i < n; i++) {
            ans += ' ';
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!lcp[i][j]) {
                    continue;
                }
                int x = i + 1, y = j + 1;
                int fx = getf(x), fy = getf(y);
                if (fx == fy) {
                    continue;
                }
                fa[fx] = fy;
            }
        }
        char now = 'a';
        for (int i = 0; i < n; i++) {
            if (vis[i]) {
                continue;
            }
            if (now > 'z') {
                return "";
            }
            for (int j = 0; j < n; j++) {
                if (getf(i + 1) == getf(j + 1)) {
                    ans[j] = now;
                    vis[j] = 1;
                }
            }
            now++;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (ans[i] == ans[j]) {
                    f[i][j] = f[i + 1][j + 1] + 1;
                }
                else {
                    f[i][j] = 0;
                }
                if (f[i][j] != lcp[i][j]) {
                    return "";
                }
            }
        }
        return ans;
    }
};