题解 P7091 【数上的树】

Alex_Wei · 2020-11-23 22:43:58 · 题解

Update on 2023.4.4 勘误：g_i 实际上等于 d_i 质因子数量的两倍减去 1。

题目传送门。

首先将 n 分解质因数，用 DFS 求出 n 的所有因数，记为 d_1,d_2,\cdots,d_c，跑一遍反素数那题的代码可知 c\leq 23327（

设 f_i 表示根节点为 d_i 时最小值。

显然，局部最优值可以保证整体最优值，且转移无后效性，即求 f_i 时不会影响 f_j\ (d_j<d_i)，故答案可以用树形 DP 求出，将所有因数排序后可以转化为序列上的 DP。

对于不能出现在树上的 d_i 直接 skip 即可。

设 g_i 表示 d_i 所含有的质因子个数。For example，12=2\times 2\times 3，所以 12 有 3 个质因子。在本题中，g_{i} 也表示以 d_i 为根的子树的节点个数，不难发现其为定值。

假设当前转移 f_i 决策点为 j,k\ (d_j\times d_k=d_i)，那么对于 d_j 和 d_k 子树内两两组合出的 pairs 的贡献可以直接由 f_j+f_k 推得，剩下来只有两种情况：

Case 1：d_j 和 d_k 子树内各一个节点组合出的 pairs。因为它们的 LCA 是 d_i，且共有 g_j\times g_k 对 pairs，故贡献为 g_j\times g_k\times d_i。
Case 2：d_i 和任意一个节点组合出的 pairs。显然贡献为 g_i\times d_i。

转移方程：

f_i=\min_{d_j\times d_k=d_i}f_j+f_k+(g_j\times g_k+g_i)\times d_i

其中 g_i=g_j+g_k+1 可以在 DP 时一并求出。

这样子搞是 \mathcal O(c^3) 的，显然无法接受。

剪枝 1：在枚举内层循环 j 时发现 k 有单调性，所以直接用指针代替 k 即可。这样时间复杂度降为了 \mathcal O(c^2)。
剪枝 2：当 j>k 时直接 break，减小常数。

综上，我们有了一个 {\mathcal O}(\sqrt n+m\log c+c^2) 的算法（分解质因数 + 处理限制需要二分查找 + DP），代码如下：

ll n,m,num[N],f[N];
ll cnt,pr[N],c[N],tot;
ll fc[N],il[N],d;
map <ll,int> isp;

void dfs(int pos,ll prod){
    if(pos>cnt){
        if(prod>1)fc[++d]=prod;
        return;
    } for(int i=0;i<=c[pos];i++)dfs(pos+1,prod),prod*=pr[pos];
}

int main(){

    cin>>n>>m;
    // factor
    ll tmp=n;
    for(ll i=2;i*i<=n;i++)
        if(n%i==0){
            pr[++cnt]=i,isp[i]=1;
            while(n%i==0)c[cnt]++,tot++,n/=i;
        }
    if(n>1)pr[++cnt]=n,tot++,c[cnt]=1,isp[n]=1;
    n=tmp;

    // find factors
    dfs(1,1);
    sort(fc+1,fc+d+1);

    // limit
    for(int i=1;i<=m;i++){
        ll val=read();
        int pos=lower_bound(fc+1,fc+d+1,val)-fc;
        if(pos<=d&&fc[pos]==val)il[pos]=1; // 表示 pos 不能出现
    }

    // dp
    for(int i=1;i<=d;i++){
        if(il[i])continue;
        if(isp[fc[i]]){
            num[i]=1,f[i]=fc[i];
            continue;
        } il[i]=1,f[i]=inf; // 如果无法由以前的 j,k 转移得到那么 i 也无法得到
        int p=i-1;
        for(int j=1;j<i;j++){
            if(fc[i]%fc[j])continue;
            while(fc[p]>fc[i]/fc[j])p--;
            if(j>p)break;
            if(!il[j]&&!il[p])f[i]=min(f[i],f[j]+f[p]+num[j]*num[p]*fc[i]+(num[i]=num[j]+num[p]+1)*fc[i]),il[i]=0;
        }
    } if(il[d])puts("-1");
    else cout<<(ll)f[d]<<endl;
    return 0;
}