Readme

3671.Sum-of-Beautiful-Subsequences

此题包含了两个知识点。我们拆开来分析。

第一个问题，对于任意的正整数g，如何计算在数组里有多少个strictly increasing subsequence并且序列中每个元素都是“g的倍数”。假设我们已经通过预处理，知道数组里g的倍数位于[i1,i2,...,ik]的位置上。注意我们只需要构造严格递增的序列，所以我们需要只知道它们之间的大小关系和位置关系，但是不需要知道绝对大小和绝对位置，故我们可以离散化，转化为类似[1,3,5,2,4]这样的形式，表示数组里有5个数是g的倍数，且它们的相对位置和相对大小都可以用这样的形式表示出来。于是我们就构造出了这样一个问题：里面有多少个严格递增的序列？

这是一个经典问题，我们可以用树状数组来解。我们想象一个长度为5的空数组，需要依照上述次序涂黑。首先我们在填写1时，以它结尾的递增序列只有一个，记作f(1)。然后我们填写3时，以它结尾的递增序列就是f(3)=f(1)+1，表示以1结尾的递增序列再附加上3，或者单独的3也可以构成一个符合条件的序列。然后我们填写5时，以它为结尾的递增序列就是f(5)=f(1)+f(3)+1。然后我们填写2时，以它结尾的递增序列就是f(2)=f(1)+1...由此我们可以看出f(x)就是BIT数组前缀和f(1)+f(2)+...+f(x-1)再加1.于是我们就可以求出所有的f(x)并且求和，就得出：数组里有多少个严格递增序列、并且每个元素都是“g的倍数”，我们记作p(g).

在有了p(g)的基础上，我们如何进一步求出数组里有多少个严格递增序列、并且所有元素的GCD恰好是g呢？我们记作这样的解是ret(g)，其实就是删去在p(g)里去除“2以上g的倍数”的情况，即ret(g) = p(g)-ret(2g)-ret(3g)-...-ret(kg). 所以我们只需要对g按从大到小的顺序求解q：当解到ret(g)时，p(g)和ret(2g)...ret(kg)就都是已知的了。初始条件是对于数组里的最大元素mx，ret(mx) = 1.

最终返回g*ret(g)对于g=1,2,..,mx的之和