【组合计数】CF1780F Three Chairs

· · 题解

\text{Part 0. Description}

给定长度为 n 的正整数序列 a，序列元素互不相同，问有多少个由序列 a 的元素组成的三元组 (a_i,a_j,a_k) 满足该条件：

\text{Part 1. Analysis}

\text{Part 1.0 暴力}

看完题目我们很快就能得到 O(n^3) 的做法：

  1. 将序列 a 从小到大排序。
  2. ans=\sum\limits_{i=1}^{n}\sum\limits_{j=1,j\neq i}^{n}\sum\limits_{k=1,k\neq i,k\neq j}^{n} [\gcd(a_k,a_i)=1]

\text{Part 1.1 问题转化}

我们将三元组 (a_i,a_j,a_k) 的最大最小值分别表示为 a_{\max} 和 a_{\min}。

容易看出一个三元组 (a_{\min},a_k,a_{\max}) 是否合法，仅与它的 a_{\min} 和 a_{\max} 有关，而中间的 a_k 只需要保证 a_{\min}<a_k<a_{\max} 即可。

因为我们已经将序列 a 从小到大排了序，所以条件 a_{\min}<a_k<a_{\max} 可转化为 \min<k<\max，即用下标的大小关系表示数值的大小关系。

也就是说对于每一对满足 a_i<a_j 的序列元素组 (a_{i},a_{j})，当我们将 a_i,a_j 分别作为一个三元组的最大最小值时，三元组 (a_{\min}[a_{\min}=a_{i}],a_k,a_{max}[a_{\max}=a_j]) 对我们最终要求得的合法三元组个数的贡献为（三元组中的 a_k 不定）：

合法三元组 (a_{\min}[a_{\min}=a_{i}],a_k,a_{\max}[a_{\max}=a_j]) 的数量

$=$ 满足 $\min<k<\max$ 的$ k$ 的个数 $=\max-\min-1

注意，上面的式子是在满足 \gcd(a_{\min},a_{\max})=1 的前提下得到的。

分析到这里我们发现问题可以转化为枚举每一对满足 a_i<a_j 的序列元素组 (a_{i},a_{j})，也就是枚举每个三元组的 a_{\min} 和 a_{\max}，然后计算三元组 (a_{\min},a_k,a_{\max}) 对我们最终要求得的合法三元组个数的贡献（三元组中的 a_k 不定），故我们得到：

ans=\sum\limits_{i=1}^{n}\sum_{j=i+1}^{n}(j-i-1)[\gcd(a_i,a_j)=1]

直接求解上式的时间复杂度为 O(n^2)，仍然无法通过此题，于是我们考虑继续优化。

\text{Part 1.2 式子转化}

这里有一个前置知识 QwQ：莫比乌斯函数（符号为 \mu ）。

对于其定义，这里直接放图。

不太了解莫比乌斯函数的话可以去 cmd 爷 の blog 那里学习一下噢。（看完题解再去学啊喂！）

这里有一个关于莫比乌斯函数的性质需要我们了解一下：

\sum\limits_{d|n}\mu(d)=[n=1]

要证明的话，直接理解函数定义 + 分类讨论就可以啦，这里不作过多阐述。

由莫比乌斯函数的这个性质我们得到一个转化式子的新思路：

实际上这也是一个比较常见的套路呐。

那么此时 \text{Part 1.1} 中推导出来的式子我们就可以继续进行转化啦！

ans=\sum\limits_{i=1}^{n}\sum_{j=i+1}^{n}(j-i-1)[\gcd(a_i,a_j)=1] =\sum\limits_{i=1}^{n}\sum_{j=i+1}^{n}(j-i-1)\sum\limits_{d|a_i,d|a_j}\mu(d)

通过交换求和符号我们可得：

ans=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(j-i-1)[d|a_i][d|a_j]

不难发现，在和式的 \sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(j-i-1)[d|a_i][d|a_j] 的部分中我们大量地重复枚举了 d 的倍数，于是我们考虑继续在这里进行优化。

在枚举 d 的时候，我们考虑弄一个 num 数组将所有小于等于 a 数组中的最大值的 d 的倍数存储下来。

即 num=\{ d,2d,\cdots,k\cdot d\}(k\cdot d \leq n)。

显然有 num 序列中的元素个数为 k，且 k=\left\lfloor\dfrac{n}{d}\right\rfloor。

此时我们可以继续推出新的式子：

ans=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(j-i-1)[d|a_i][d|a_j] =\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{k}\sum\limits_{j=i+1}^{k}num_j-num_i-1

此时我们可以将和式的 num_j-num_i-1 拆解为 num_j-num_i 和 -1 两部分来计算：

  1. 我们先计算 -1 部分的总值。

当 i=1 时， \sum\limits_{j=i+1}^{k}(-1)=-(k-1) ;

当 i=2 时， \sum\limits_{j=i+1}^{k}(-1)=-(k-2) ;

\dots\dots

当 i=k 时， \sum\limits_{j=i+1}^{k}(-1)=0。

显然有和式 \sum\limits_{i=1}^{k}\sum\limits_{j=i+1}^{k}(-1)=-[(k-1)+(k-2)+\cdots+-0]，即为项数为 k 公差为 1 的等差数列求和然后再取负数，故我们直接用求和公式就可以直接算出 -1 的总值：

\sum\limits_{i=1}^{k}\sum\limits_{j=i+1}^{k}(-1)=-\dfrac{k\cdot(k-1)}{2}
  1. 接着我们计算 num_j-num_i 部分的值：

根据套路我们发现 \sum\limits_{i=1}^{k}\sum\limits_{j=i+1}^{k}num_j-num_i 的求值其实就是求取 1\leq x\leq k 范围内的每一个 num_x 的贡献。

于是我们将 num_j-num_i 分为 num_j 和 -num_i 两部分来求解：

2.1 num_x 作为 num_j 被累加时：

2.2 num_x 作为 num_i 被减去时：

应该不会有人已经忘记了原来的和式中 num_i 的系数为 -1 吧。 QwQ

最后我们得到 num_x 作为 num_i 和 num_j 被计算之后总的贡献就是：

num_x\cdot[(x-1)+(x-k)] =num_x\cdot(2x-k-1)

此时我们再重新看回到我们的式子推导：

ans=\sum\limits_{i=1}^{n}\sum_{j=i+1}^{n}(j-i-1)[\gcd(a_i,a_j)=1] =\sum\limits_{i=1}^{n}\sum_{j=i+1}^{n}(j-i-1)\sum\limits_{d|a_i,d|a_j}\mu(d) =\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}(j-i-1)[d|a_i][d|a_j]

弄一个 num 数组将所有小于等于 a 中的最大值的 d 的倍数存储下来，其元素个数为 k：

=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{k}\sum\limits_{j=i+1}^{k}num_j-num_i-1

计算 1\sim k 中的每一个 num 的贡献以及 -1 的贡献：

ans=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{k}\sum\limits_{j=i+1}^{k}num_j-num_i-1 =\sum\limits_{d=1}^n\mu(d) \left[-\dfrac{k\cdot(k-1)}{2}+\sum\limits_{x=1}^{k}num_x\cdot(2x-k-1)\right] 此时求解答案的时间复杂度为 $O(n\log n)$。 ## $\text{Part 2. Code} 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=300005;
int n,a[M],ans,mu[M],f[M],num[M];
bool bo[M];
vector<int>pri;
void pre();
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) f[a[i]]=i;
    pre();
    for(int i=1;i<=a[n];i++){
        if(!mu[i]) continue;
        int k=0,sum;
        for(int j=i;j<=a[n];j+=i){
            if(f[j]) num[++k]=f[j];
        }
        sum=-(k-1)*k>>1;
        for(int j=1;j<=k;j++)
            sum+=num[j]*(j+j-k-1);
        ans+=mu[i]*sum;
    }
    printf("%lld",ans);
    return 0;
}

void pre(){
    mu[1]=1; int ss=0;
    for(int i=2;i<=M-4;i++){
        if(!bo[i]) mu[i]=-1,++ss,pri.push_back(i);
        for(int j=0;j<ss&&i*pri[j]<=M-4;j++){
            bo[i*pri[j]]=1;
            if(!(i%pri[j])) break;
            mu[i*pri[j]]=-mu[i];
        }
    }
}