202104-4 校门外的树

10% 数据——输出真因子个数

\(n = 2\) 时只有一个区间 \([a_1,a_2]\)。

设 \(d = a_2 - a_1\)，答案即为 \(d\) 的真因子个数。

30% 数据——搜索

按照题目要求，有两种美观区间：

区间 \([a_l,a_r]\) 内中的树构成等差数列，且树集合中不含有其他 \(a_i\)；
区间 \([a_l,a_r]\) 内存在 \(a_m\)，满足 \([a_l,a_m]\) 和 \([a_m,a_r]\) 都是美观区间；

为了方便描述，称第一种为一型美观区间，称第二种为二型美观区间。

容易想到的一种方法是，通过搜索去判断每一个区间的类型：

对于一型美观区间，我们枚举每个因子，判断其是否会与障碍物重合；
对于二型美观区间，我们枚举中间点，将左右区间结果相乘即可。

但是当处理二型美观区间的时候，可能会出现这样的问题：

例子

假设要在 \(a_1,a_2,a_3,a_4\) 种树，求 \([a_1,a_4]\) 是美观区间的方案数。

在枚举 \([a_1,a_4]\) 的二型美观区间中间点的时候，会出现两种划分方式：

\([a_1,a_3]\) 是二型美观区间，\([a_3,a_4]\) 是一型美观区间。其中在 \([a_1,a_3]\) 是二型美观区间的搜索中，会出现 \([a_1,a_2]\) 和 \([a_2,a_3]\) 是一型美观区间的情况。
\([a_1,a_2]\) 是一型美观区间，\([a_2,a_4]\) 是二型美观区间。其中在 \([a_2,a_4]\) 是二型美观区间的搜索中，会出现 \([a_2,a_3]\) 和 \([a_3,a_4]\) 是一型美观区间的情况。

在两种划分方式中，都出现了 \([a_1,a_2]\)，\([a_2,a_3]\) 和 \([a_3,a_4]\) 都是一型美观区间的情况，导致重复计数。

从另一个角度来看，二型美观区间就是由许多一型美观区间拼接而来，我们只需要考虑一型美观区间即可，所以任务转变为选取一些一型美观区间，拼凑出整个区间。上述方法的错误点在枚举了重复的子集，我们思考该如何枚举。

一种朴实无华的方法是，枚举所有的区间端点情况。

思考时间复杂度：设 \(\max\{a\}=A\)，枚举所有端点情况 \(\mathrm{O}(2^n)\)，每个情况需要计算 \(\mathrm{O}(n)\) 段一型美观区间，计算一个区间的复杂度是 \(\mathrm{O}(nd(A))\)，其中 \(d(x)\) 表示 \(x\) 的真因子个数，在 \(x=83160\) 时取到最大值 \(127\)。至于所有真因子的计算，我们可以预处理完成。复杂度 \(\mathrm{O}(A\sqrt A)\)。最终整体复杂度 \(\mathrm{O}(A\sqrt A+2^nnd(x))\)。

60% 数据——动态规划

枚举所有的端点情况不现实了。

我们不妨换个角度，再思考上个错误的做法：我们枚举了重复的子集。换句话说，对于一个特定的状态，它映射到了多种美观区间的组合。如果能做到一个状态唯一对应一种美观区间，那么问题就解决了。

由于美观区间都是由一些一型美观区间拼接而成的，所以可以进行这样对应：

如果美观区间包含一个一型美观区间，则对应一个一型美观区间；
如果美观区间包含两个一型美观区间，则对应两个一型美观区间；
如果美观区间包含 \(n(n\ge 3)\) 个一型美观区间，则第 \([1,n-1]\) 区间对应一个二型美观区间，第 \(n\) 个区间对应一个一型美观区间。

注：以上只是一种对应方案，对应方案不唯一。

在确定划分方案后，考虑如何计数。不妨设 \(f(i)\) 表示区间 \([a_1,a_i]\) 是美观区间的方案数，\(g(i,j)\) 表示区间 \([a_i,a_j]\) 是一型美观区间的方案数，那么可以得到转移方程：

\[f(i)=\sum\limits_{j=1}^{i-1}{f(j)\cdot g(j,i)}\]

考虑时间复杂度：状态转移 \(\mathrm{O}(n^2)\)，计算 \(g(i,j)\) 复杂度 \(\mathrm{O}(nd(A))\)，预处理所有因子 \(\mathrm{O}(A\sqrt A)\)，整体复杂度 \(\mathrm{O}(A\sqrt A+n^3d(A))\)。如果不预处理所有因子，而是直接计算的话，复杂度 \(\mathrm{O}(n^3\sqrt A)\)。

100% 数据——优化一型美观区间方案数的计算

思考哪一步浪费了时间：设 \(i<j<k\)，在计算 \(g(j,k)\) 的时候需要枚举 \(a_k-a_j\) 的所有因子，而在计算 \(g(i,k)\) 的时候，我们仍然需要用 \(a_k-a_i\) 的所有因子与 \(a_k-a_j\) 进行对应的比较。

我们不妨探讨一下区间扩充带来的变化。

区间扩充的变化

设 \(i<j<k\)，在求 \([a_i,a_k]\) 时，考虑 \(a_j\) 的影响。比较容易想到的是在种树的时候，我们不能经过 \(a_j\)。

至于会经过 \(a_j\) 的种树方案，在不考虑满足 \(a_k-a_i\) 真因子的条件下，其实就是 \([a_i,a_j]\) 区间的因子往大延伸和 \([a_j,a_k]\) 的因子往小延伸。

总结一下，对于一个满足是 \(a_k-a_i\) 真因子的数 \(d\)，如果满足以下任意一个条件，则是非法的：

\(d\) 是 \(a_j-a_i\) 的因子；
\(d\) 是 \(a_k-a_j\) 的因子。

然而有一点可以化简：若 \(d\) 是 \(a_k-a_i\) 的真因子且 \(d\) 是 \(a_k-a_j\) 的因子，那么 \(d\) 也是 \(a_j-a_i=(a_k-a_i)-(a_k-a_j)\) 的因子。我们只需要判断其中一个区间即可。

由上可以得出，在枚举的时候，我们可以从小到大逐步扩大空间，并记录已经使用过的因子，从而在枚举因子的时候不用枚举每一个中间点。

我们设记录的复杂度是 \(\mathrm{O}(r(n))\)，使用 set 等复杂度是 \(\mathrm{O}(\log n)\) 的，而使用哈希等方法是 \(\mathrm{O}(1)\) 的。

考虑时间复杂度：状态转移 \(\mathrm{O}(n^2)\)，计算 \(g(i,j)\) 复杂度 \(\mathrm{O}(d(A)r(nd(A)))\)，预处理所有因子 \(\mathrm{O}(A\sqrt A)\)，整体复杂度 \(\mathrm{O}(A\sqrt A+n^2d(A)r(nd(A)))\)。

代码实现

C++

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define il inline
const int maxn = 1010;
const ll mod = 1e9 + 7;
int n;
int a[maxn];
ll f[maxn];
set<int> st;
vector<int> fac[100010];
int g(int l, int r) {
    int d = a[r] - a[l];
    int res = 0;
    st.insert(d); // 将本身加入
    for (int i = 0; i < fac[d].size(); ++i) {
        if (!st.count(fac[d][i])) {
            // 如果因子没有被统计过，说明在本区间是合法的
            // 同时，这也导致包含该区间的更大区间是非法的
            st.insert(fac[d][i]);
            ++res;
        }
    }
    return res;
}
void init() {
    // 预处理，求出所有的真因子
    for (int i = 1; i <= 50000; ++i) {
        for (int j = 2; i * j <= 100000; ++j) {
            fac[i * j].push_back(i);
        }
    }
}
int main() {
    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        st.clear();
        for (int j = i - 1; j >= 1; --j) { // 区间从小到大
            f[i] = (f[i] + f[j] * g(j, i) % mod) % mod;
        }
    }
    printf("%lld", f[n]);
    return 0;
}

202104-4 校门外的树

10% 数据——输出真因子个数

30% 数据——搜索

60% 数据——动态规划

100% 数据——优化一型美观区间方案数的计算

评论