本题链接：202104-4 校门外的树

本博客给出本题截图：

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 1010, M = 100010, MOD = 1e9 + 7;

int n;
int a[N];
int f[N];
vector<int> q[M];
bool st[M];

int main()
{
    for (int i = 1; i < M; i ++ )
        for (int j = i * 2; j < M; j += i)
            q[j].push_back(i);

    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    f[0] = 1;
    for (int i = 1; i < n; i ++ )
    {
        memset(st, false, sizeof st);
        for (int j = i - 1; j >= 0; j -- )
        {
            int d = a[i] - a[j], cnt = 0;
            for (int k: q[d])
                if (!st[k])
                {
                    cnt ++ ;
                    st[k] = true;
                }
            st[d] = true;
            f[i] = (f[i] + (LL)f[j] * cnt) % MOD;
        }
    }

    printf("%d\n", f[n - 1]);
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

总结

典型的 dp + 约数，注意预处理

超级长的题干抽象出来之后该问题为：对于一个起始点为 a[1]，终点为 a[n] 的这么一条线段上，你可以选择若干个点，比如我们选择了两个点 a[k] 和 a[j]，其中 k < j，那么我们就把这个线段分成了三段，分别为 a[1] ~ a[k]，a[k] ~ a[j]，a[j] ~ a[n]，那么对于这么三段，每一段我们都可以把它进行等分，即存在一个点 t，使得 a[1] ~ t 的长度等于 t ~ a[k]，（这是二等分，当然你也可以继续等分下去，当然这里必须保证是约数），并且 t 这个点不可以和 a[s]，s ∈ (1, k) 重合，问满足这样约数条件有多少种情况是符合题意的

显然是一道 dp 问题，首先我们需要预处理约数，因为后续涉及到等分的操作，避免后期重复运算直接把范围内的约数都计算出来，放入到 q 中；然后去考虑需要几维的转移，实在不知道几维的话不妨从一维开始试，设 f[i] 表示的是前 i 个障碍点的所有方案，那么显然有初始化 f[0] = 1，然后状态转移：f[i] 可以从 f[0] ~ f[i - 1] 的状态中进行转移，假设 j ∈ [0, i)，那么转移过程就变成了前 j 个点的方案数再乘上 a[j] ~ a[i] 这么一段可以划分成的个数，最后的 f[i] 就是对所有的情况求和（注意取模）

本题重中之重还在于 st 数组的使用，因为是要求和的原因，所以我们在不漏的前提下必须加入不重，那么对于 a[i] 而言，我们是从后往前进行遍历的，遍历的过程中，我们需要记录 k 这个长度是否是被用过的，如果用过，我们需要直接 continue，因为对于同一个 a[i] 而言如果我们在 a[r] 时是用过 k 的话，那么我们再次把每份分成长度为 k 的时候，比如此时是 a[l]，那么我们 a[l] ~ a[i] 这段一定有一个划分点是 a[r]，但是我们题目要求不可以有这种情况，故我们开一个 st 数组，每一个 a[i] 在进行状态转移的时候我们都需要清空一下，其作用就是记录分成长度为 k，这个长度是否被用过，如果没有用过，就让 cnt ++, st[k] = true;，最后记得要让st[a[i] - a[j]] = true;

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/120117742