Square-free division (hard version) 题解

Creeper_l · 2023-11-27 14:52:47 · 题解

题意：给定一个长度为 n 的序列，求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。你还可以将其中 k(k \le 20) 个数修改为任意的值。

一个小 Trick：如果两个数乘起来为平方数，可以先将每个数的平方因子除掉，然后这两个数必然相等。于是可以先将每个 a_{i} 的平方因子除掉，然后这道题被转化为了一个区间不能有相等的值。

首先考虑没有修改的情况怎么做，设 pos_{a_{i}} 表示上一个 a_{i} 出现在哪里（也就是最远可以满足条件的位置），那么有 dp 转移方程 dp_{i}=dp_{pos_{a_{i}}}+1，时间复杂度 O(n)。

然后考虑有修改操作的情况，我们可以稍微改变一下 pos 数组的定义，改为 pos_{i,j} 表示当前点为 i，修改 j 次后可以到达的最远的满足条件的位置。那么怎么转移呢？pos_{i,j}=\min(pos_{i-1,j-1},last+1)，last 表示上一个 a_{i} 出现的位置。因为 pos_{i-1,j-1} 和 last+1 这两个位置都有可能是修改次数的分界点，看哪个更小即可。然后就可以用 pos 数组来 dp 转移了：dp_{i,j}=dp_{pos_{i,k},j-k}+1。最终的答案就是 dp_{n,k}，时间复杂度 O(nk^{2})。

注意分解质因数的时候可以先将质数线性筛出来，这样效率更高。

#include<bits/stdc++.h>
using namespace std;
#define re register
const int MAXN = 2e5 + 10,MAXM = 25;
int T,n,k,dp[MAXN][MAXM],a[MAXN],prime[MAXN],cnt,b[MAXN];
int pos[MAXN],last,p[MAXN];
bool is_prime[MAXN];
inline void Get_prime(int n)
{
    memset(is_prime,1,sizeof is_prime);
    is_prime[1] = 0;
    for(re int i = 2;i <= n;i = -~i)
    {
        if(is_prime[i] == 1) prime[++cnt] = i;
        for(re int j = 1;j <= cnt && i * prime[j] <= n;j = -~j)
        {
            is_prime[i * prime[j]] = 0;
            if(i % prime[j] == 0) break;
        }
    }
}
signed main()
{
    cin >> T;
    Get_prime(10000);
    while(T--)
    {
        cin >> n >> k;
        for(re int i = 1;i <= n;i = -~i) cin >> a[i];
        for(re int i = 1;i <= n;i = -~i)
        {
            for(re int j = 1;j <= cnt;j = -~j)
            {
                re int val = prime[j];
                while(a[i] % (val * val) == 0) a[i] /= (val * val);
                if(prime[j] * prime[j] > a[i]) break;
            }
            b[i] = a[i];
        }
        sort(b + 1,b + n + 1);
        int q = unique(b + 1,b + n + 1) - b - 1;
        for(re int i = 1;i <= n;i = -~i) a[i] = lower_bound(b + 1,b + q + 1,a[i]) - b,pos[a[i]] = 0;
        for(re int i = 0;i <= k;i = -~i) p[i] = 1,dp[0][i] = 0;
        for(re int i = 1;i <= n;i = -~i)
        {
            re int last = pos[a[i]];
            for(re int j = k;j >= 0;j--)
            {
                if(p[j] > last) continue;
                if(j == 0) p[j] = last + 1;
                else p[j] = min(last + 1,p[j - 1]);
            }
            for(re int j = 0;j <= k;j = -~j)
            {
                dp[i][j] = 1e18;
                for(re int k = 0;k <= j;k++) dp[i][j] = min(dp[i][j],dp[p[k] - 1][j - k]);
                dp[i][j] = dp[i][j] + 1; 
            } 
            pos[a[i]] = i;
        }
        cout << dp[n][k] << endl;
    }
    return 0;
}