CF1986G2 Permutation Problem (Hard Version)

· · 题解

Question 问题 CF1986G2 Permutation Problem (Hard Version)

难度：\colorbox{#8942cc}{\color{White}省选/NOI−}

给定一个 1\sim n 的排列 p，求整数对 (i,j) 的数量，满足 1\le i<j\le n 且 p_i\cdot p_j 能被 i\cdot j 整除。每个测试点 t 组测试用例。

数据范围

Analysis 思路分析

首先对于 \frac{p_i \cdot p_j}{i \cdot j} 是否为整数，我们会发现可能 i,j 可能存在 p_i 的因数，这让我们解题变得更加复杂。我们想让影响的因素尽可能减少。

发现该形式可以写作 \frac{p_i}{i} \cdot \frac{p_j}{j}，所以我们可以先将 \{p_i,i\} 分别除去他们两个的 \gcd。这一步是为了避免 p_i 和 i 之间存在可能可以除的关系。

也就是令 a_i=\frac{i}{\gcd(p_i,i)}，b_i=\frac{p_i}{\gcd(p_i,i)}，该问题就转化为了求 a_i \mid b_j 并且 a_j \mid b_i 的 \{i,j\} 有序二元组。思考如何计算。

Solution 数学

感觉整体的思路就是 b_i \stackrel{扩倍}\to a_i \stackrel{查询}\to \{a_j,b_j\} 如同通关游戏一样。我们可以先枚举 b_i 在借此枚举出 b_i 的倍数 a_i，并在此基础上查询有多少个 b_j 符合 a_i \mid b_j，那这样子的话就符合了我们的 a_i \mid b_j 并且 a_j \mid b_i 的条件，关键在于如何查询。

最初的想法是维护一个二维数组 cnt_{i,j} 表示满足 a_k=i 并且 j \mid b_k。但是很容易发现我们连数组都开不下。即使考虑使用 map 维护，最坏的情况下空间会因为 map 被插入内容过大而爆炸，这也是很多人在此题 128MiB 的限制下 MLE 了。

考虑如何优化，我们会发现 cnt_{x,...} 只会在所有 x \mid b_j 的 j 有贡献出现。那这样子我们只需要去枚举 j 即可，压掉一维。

或者换一种方式思考，我们当前先枚举 b_i 后可以通过我们建立的 \{a_i\} 和 \{b_i\} 双射找到其对应的所有 \{a_i\}。那这样下来，我们未知的就只剩下 \{a_j,b_j\} 了。所以我们再度枚举 a_j 并保证他是 b_i 的倍数，去找对应满足 b_j \mid a_i 的 b_j 数量了。

我们预处理出该 b_i 对应的所有 \{a_i\} 的因数个数和。令 cnt_i 表示有多少个 a_i 拥有 i 这个因数。接下来枚举 a_i 的倍数，并计算出此时 k\cdot b_i=a_j 对应的所有 \{b_i\}，那么 a_j 对答案的贡献就是 cnt_{b_i}。

在最后，由于本题询问的是有序二元组，以上做法并没有考虑 i < j，所以最终答案需要除以二。同时当 i=j，只会在 a_i \mid b_i 时产生一个贡献。所以提前减掉即可。

记得清空。

时间复杂度：

因为 [1,n] 之间的因数个数和的复杂度为 O(n\ln n)，下面统计答案首先枚举 b_i，并且还去寻找其对应的所有因数，整体的复杂度与上面同阶为 O(\sum fac_{a_i}) \le O(n \ln n)，所以整体复杂度为 O(n \ln n)。

Code 代码

signed main(){
    for(rint i=1;i<=N-7;i++) for(rint j=i;j<=N-7;j+=i) fac[j].pb(i);
    read(T);
    while(T--){
        ans=0;
        read(n);
        for(rint i=1,t;i<=n;i++){
            read(t);
            int x=i/__gcd(i,t),y=t/__gcd(i,t);//除去 gcd
            a[x].pb(y);b[y].pb(x);//建立双射，有利于计算答案
            if(x==1) ans--;//对于 i=j 且 ai|bi 的情况提前减掉
        }
        for(rint i=1;i<=n;i++){
            for(auto a1:a[i]) for(auto a2:fac[a1]) cnt[a2]++;//处理因数个数和
            for(rint a2=i;a2<=n;a2+=i) for(auto b1:b[a2]) ans+=cnt[b1];//计算贡献
            for(auto a1:a[i]) for(auto a2:fac[a1]) cnt[a2]=0;//清空
        }
        for(rint i=1;i<=n;i++) a[i].clear(),b[i].clear();//清空
        cout<<ans/2<<endl;//注意有序，除以二
    }
    return 0;
}