D、马騳骉子序列 题目描述 有一个长度为 的序列 ，请求出 中有多少个马騳骉子序列。 一个序列 被定义为马騳骉序列，当且仅当：对于序列中每一个位置 ， 都能够被 整除 由于答案可能过大，所以对 取模 输入描述 第一行输入一个整数 第二行输入 个整数表示序列 输出描述 输出一个整数表示答案。 输入样例 输出样例 样例解释 样例中的13种方案分别为 D、马騳骉的子序列 首先考虑暴力动态规划，设置状态 dp[i][j] 为枚举到 i 点，b序列长度为 j 的方案个数。 则状态转移方程为： dp[i][j] = dp[i-1][j] + (a[i] % j == 0) * dp[i-1][j-1] 但是这样显然会空间超限，考虑如何优化。 我们发现dp[i][j]，只会由dp[i-1] 转移来。 所以可以通过滚动数组优化掉第一维。 且第二维 j 的更新只与前面的有关，所以可以通过倒着枚举优化。 即：用dp[j]表示枚举到目前为止，长度为j的合法序列的数量。 #include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstring> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <vector> #define CLOSE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); #define isd(c) ('0' <= (c) && (c) <= '9') #define isa(c) ('a' <= (c) && (c) <= 'z') #define isA(c) ('A' <= (c) && (c) <= 'Z') #define mem(a, b) memset(a, b, sizeof a); #define N 100005 #define M 2000005 #define mod 1000000007 #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3f #define ll long long #define ull unsigned long long #define PI acos(-1) #define endl "\n" #define pii pair<int, int> #define F first #define S second #define bug cout << endl << " .....here!...." << endl; //#pragma GCC optimize("O3") //#define Time ((double)clock() / CLOCKS_PER_SEC <= 0.95) using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; ll dp[M], num[M]; int main() { CLOSE int n; cin >> n; dp[0] = 1; for (int i = 1; i <= n; i++) { int x, cnt = 0; cin >> x; for (int j = 1; j * j <= x; j++) { if (x % j == 0) { num[++cnt] = j; if (x / j != j) num[++cnt] = x / j; } } sort(num + 1, num + 1 + cnt, greater<int>()); for (int j = 1; j <= cnt; j++) dp[num[j]] = (dp[num[j]] + dp[num[j] - 1]) % mod; } ll ans = 0; for (int i = 1; i <= n; i++) ans = (ans + dp[i]) % mod; cout << ans << endl; return 0; } 我是一个算竞小白，dp新手，请你为我详细讲解这道题目，我看不懂

<think>嗯，我现在得仔细看看这个问题。题目是让我们找出一个序列中的马騳骉子序列的数量。那什么是马騳骉子序列呢？根据题目描述，这样的子序列需要满足每个位置的元素都能被该位置的下标整除。也就是说，如果子序列的长度是k，那么对于第i个元素（i从1开始），必须满足a_j % i == 0，其中a_j是原序列中的某个元素，并且作为子序列的第i个元素。 首先，我需要理解子序列的定义。子序列不一定是连续的，但顺序要一致。比如原序列是1,2,3，那么可能的子序列包括1,3或者2,3等等。但这里还附加了每个位置上的元素必须能被位置i整除的条件。 那么，怎么计算这样的子序列的数量呢？直接暴力枚举所有可能的子序列显然不可行，因为时间复杂度太高，尤其是当n比较大的时候。这时候动态规划可能是一个好的选择。 原题解中提到了一种动态规划的思路。状态定义为dp[i][j]，表示处理到原序列的第i个元素时，长度为j的合法子序列的个数。状态转移方程是：dp[i][j] = dp[i-1][j] + (a[i] % j ==0) * dp[i-1][j-1]。这表示，对于当前元素a[i]，我们可以选择不选它，这样数量就是之前的dp[i-1][j]；或者如果a[i]能被j整除（即选它作为子序列的第j个元素），那么数量是dp[i-1][j-1]。这样，每个位置的j的状态由前一个状态转移而来。 但问题在于，如果直接这样处理，空间复杂度是O(n^2)，当n很大时，比如1e5，这样的空间肯定不够。所以需要优化空间。这时候想到滚动数组，因为每次更新dp[i][j]只需要用到dp[i-1][j]和dp[i-1][j-1]，所以可以优化为一维数组，并且逆序更新，避免覆盖还未使用的旧状态。 在代码中，他们使用了dp数组，其中dp[j]表示当前处理到某个元素时，长度为j的合法子序列的数量。对于每个元素x，先找出它的所有因数，然后将这些因数按照从大到小排序，然后依次处理每个因数j。这里为什么要处理因数呢？因为只有当x能作为子序列的第j个元素时，才会对dp[j]产生贡献。也就是说，x必须能被j整除，所以j必须是x的因数。因此，对于每个x，找出其所有因数，并按从大到小的顺序处理，这样在更新dp[j]的时候，j-1的值还没有被当前x的处理所影响，这样就能正确地进行转移。 举个例子，假设当前处理的x的因数是j=3，那么在逆序处理的时候，较大的因数先处理。比如，假设x的因数有3，2，1。排序后按3、2、1处理。处理j=3时，dp[3] += dp[2]，而这时候的dp[2]还没有被当前x的其他因数处理过，所以这里能正确地将之前的dp[j-1]的值累加进来。 这样，每次处理x的时候，找出所有因数，然后逆序处理，确保在更新较大的j时，较小的j还没有被更新，从而避免了重复计算的问题。最终，所有可能的子序列长度的总和就是答案，所以将dp[1]到dp[n]的值相加即可。 不过，这里可能需要更详细的例子来说明这个过程。比如输入样例中的情况，假设输入的序列是某个特定的例子，比如样例中的输入可能是一个数组，比如输入为3，数组元素是2 2 2。那么，每个元素2的因数是1,2。然后对于每个元素，处理这些因数，从大到小。比如第一个元素是2，它的因数是2和1。处理顺序是2，然后1。处理j=2时，dp[2] += dp[1]。而初始时dp[0]=1，其他都是0。所以当处理第一个元素时，因为j=2需要dp[1]，但此时dp[1]还没有被处理过，所以这一步可能不会有贡献？或者初始的时候dp[0]是1，所以当处理因数j=1时，会更新dp[1] += dp[0]。这时候第一个元素处理完后，dp[1]就变成1，而dp[2]可能还是0？ 可能我需要更仔细地走一遍样例。比如样例输入给出的是3，输出是13。根据样例解释，可能的子序列有很多种。比如每个位置的元素都能满足对应的位置的条件。例如，长度为1的子序列每个元素都可以，所以有3种；长度为2的子序列需要第二个位置的元素能被2整除，所以可能有多个组合；长度为3的子序列则需要第三个元素能被3整除。 这时候，动态规划的方法是如何计算的？比如，初始时dp[0] =1。处理第一个元素x的时候，假设x是某个数，比如第一个元素是2。它的因数是1和2。处理顺序是2，然后1。这时候对于j=2，检查x是否能被j整除。是的，所以dp[2] += dp[1]，但此时dp[1]是0，所以这步没有变化。然后处理j=1，dp[1] += dp[0]，即dp[1]变成1。这时候，第一个元素处理后，dp[1]=1，dp[2]=0，其他不变。处理第二个元素（同样是2），此时它的因数是2和1。处理顺序是2，然后1。处理j=2时，x%2==0，所以dp[2] += dp[1]（此时dp[1]是1），所以dp[2]变为1。处理j=1时，dp[1] += dp[0]，所以变成1+1=2。处理第三个元素（同样为2）时，因数还是2和1。处理j=2时，x%2==0，所以dp[2] += dp[1]（此时dp[1]=2），所以dp[2] =1+2=3。处理j=1时，dp[1] += dp[0] → 2+1=3。最终，dp[1]=3，dp[2]=3，dp[3]=0。然后总共有3+3=6？显然这和样例输出不符。这说明我的例子可能不正确，或者我的理解有误。 可能原题的样例输入不同。比如原题给出的样例输入可能不是3个2的情况。可能我需要重新查看问题中的输入样例。根据用户提供的输入样例部分，可能用户没有给出具体的输入输出，所以需要假设。或者可能原题中的样例输入比如为3个数，比如2, 2, 3，或者其他情况。或者可能原题的样例输入可能为n=3，数组是2 2 2，但输出为13的情况，这时候我的之前的分析是错误的。这时候需要更详细地重新分析。 假设正确的样例输入可能如：假设输入是n=3，数组是2 2 2。那么每个元素都可以作为长度为1的子序列，所以3个。对于长度为2的子序列，每个位置i=2需要元素能被2整除。假设第一个元素是2，第二个元素是2，那么选这两个作为长度为2的子序列，第二个元素是2，必须满足2%2==0，是的。所以每个可能的两个元素的组合都可以吗？或者是不是，因为子序列的顺序必须保持原序列的顺序，所以每个子序列的两个元素必须是原序列中的不同位置，且后面元素的在原序列中的位置在之前元素之后。比如对于三个2的情况，长度为2的子序列的数量是C(3,2)=3种。但每个这样的子序列是否符合条件？因为第二个元素必须被2整除，所以是的。所以3种长度为2的子序列。长度为3的子序列需要第三个元素能被3整除。原数组中的元素是2，2，2，都不满足被3整除，所以长度为3的子序列数目是0。总共有3+3=6，但样例输出是13，这显然不符，所以我的假设的输入例子不正确。 这说明原题的输入样例可能有不同的情况。可能原题的样例输入是其他数组，例如n=3，数组是1,2,3。那么各个长度的子序列数目： 长度为1：每个元素都可以，所以3个。 长度为2：子序列的第二个元素必须能被2整除。可能的子序列包括（第一个元素可以是任意满足能被1整除的元素，即任何元素，第二个元素必须能被2整除）。 比如原数组是1、2、3： 可能的长度为2的子序列： （1,2）：2%2=0 → 有效。 （1,3）：3%2=1 → 无效。 （2,2）：第二个元素是2，有效。 （2,3）：3%2=1 → 无效。 （1,3中的第二个元素是否有效？比如选第二个元素是3的情况，作为子序列的第二个元素，必须能被2整除，但3%2=1，所以无效。所以只有两个可能的长度为2的子序列：1-2，2-2，以及 1-2中的顺序？或者原数组是三个元素的话，可能第一个元素可以是第一个1，第二个元素是第二个2；或者第一个元素是第一个1，第二个元素是第三个3（但3%2=1，不行）；或者第一个元素是第二个2，第二个元素是第三个3（同样不行）。所以对于数组1、2、3，长度2的有效子序列数目是：选1和2（第二个元素），或者选2和2（第二个元素），或者选2和3（不行），或者选1和第二个位置的2，或者选第二个位置的2和第三个位置的3。所以可能有两个有效的？ 或者可能我的分析有误，这时候应该回到动态规划的解法，通过代码来理解。 原题中的代码逻辑是：对于每个元素x，找出其所有因数，并按从大到小排序。然后对于每个因数j，执行dp[j] += dp[j-1]。这样，每个x的各个因数j，对应了当这个x作为子序列的第j个元素时，可以贡献的数目是dp[j-1]。 比如，当处理第一个元素x=2的时候，其因数是1和2。按从大到小排序，所以处理顺序是2，1。处理j=2时，dp[2] += dp[1]，但此时dp[1]的初始值为0（因为初始时dp[0]=1，其他是0）。所以这一步没有变化。然后处理j=1，dp[1] += dp[0] → dp[1] =1。此时，当前元素处理完，dp[1]=1，dp[2]=0。 处理第二个元素x=2，因数还是2和1。处理顺序是2，1。处理j=2时，dp[2] += dp[1]（此时dp[1]是1），所以dp[2]=1。处理j=1时，dp[1] += dp[0] → 1+1=2。此时，dp[1]=2，dp[2]=1. 处理第三个元素x=2，因数还是2和1。处理顺序是2，1。处理j=2时，dp[2] += dp[1]（当前是2） → 1+2=3。处理j=1时，dp[1] +=1 → 2+1=3. 最终，dp[1]=3，dp[2]=3，dp[3]=0。总和是3+3=6。但原题中的样例输出是13，所以显然这个例子不符合样例的情况。因此，这说明原题的样例输入可能不同，或者我的理解存在错误。 可能原题中的样例输入是n=3，数组是1、2、3。这种情况下，每个元素的因数： 第一个元素1的因数是1，处理顺序是1。处理j=1时，dp[1] += dp[0] → 1。 第二个元素2的因数是2和1。处理顺序是2，1。处理j=2时，dp[2] += dp[1] → 0+1=1。处理j=1时，dp[1] +=1 → 1+1=2. 第三个元素3的因数是3和1。处理顺序是3，1。处理j=3时，dp[3] += dp[2] → 1 → dp[3]=1。处理j=1时，dp[1] +=1 → 2+1=3. 此时，dp[1]=3，dp[2]=1，dp[3]=1。总和是3+1+1=5。这也不等于样例输出的13。这时候可能样例输入是其他情况，或者我理解问题的方式有误。 可能我应该重新回到题目本身的分析，而不是纠结于样例。题目要求计算所有满足条件的子序列数目，其中每个位置i的元素能被i整除。子序列的各个元素必须按照原序列的顺序，并且每个元素的位置i对应子序列的位置i。 那么，动态规划的状态dp[j]表示当前有多少个长度为j的合法子序列。对于每一个新来的元素x，我们需要考虑它能作为哪些j的位置的元素。即，对于所有满足x%j ==0的j来说，x可以作为第j个元素，此时需要将dp[j-1]的数目加到dp[j]上。 例如，假设当前处理到x=3，那么它的因数包括1,3。所以j可以是1和3。对于j=1的情况，x%1==0，所以可以贡献到dp[1]。这时候，dp[1] += dp[0]。对于j=3的情况，x%3==0，所以可以贡献到dp[3]，即dp[3] += dp[2]。这里的逻辑是，当x作为第j个元素时，前面必须有j-1个元素构成长度为j-1的子序列，这样才能形成长度为j的子序列。 那么，整个动态规划的过程是： 初始化dp[0] =1。其他dp[j]=0. 对于每个元素x： 找到x的所有因数j（包括1和x本身），因为只有这些j才能满足x%j ==0。 将这些因数按从大到小排序。例如，假设x=6，因数有1,2,3,6 → 排序后6,3,2,1. 然后，对于每个因数j，执行dp[j] = (dp[j] + dp[j-1]) % mod. 这样做的原因是为了避免重复计算。比如，当处理j=2的时候，如果先处理较小的j，那么在处理较大的j时，可能会使用已经被当前x更新过的dp[j-1]，这会导致错误。因此，必须按照j从大到小的顺序处理，这样在处理较大的j时，j-1还没有被当前x的因数处理过，从而确保使用的是之前的dp[j-1]的值。 举个例子，假设x=6，它的因数是6,3,2,1。处理顺序是6→3→2→1。 当处理j=6时，dp[6] += dp[5]。此时，dp[5]的值可能是0，所以不影响。假设此时dp[5]是0，那么dp[6]保持不变。之后处理j=3，这时候dp[3] += dp[2]。假设此时dp[2]的值是之前的，没有被当前x的处理所影响。然后处理j=2，dp[2] += dp[1]。最后处理j=1，dp[1] += dp[0]。 这样，每个因数j的处理都是在当前元素x的因数中较大的先处理，保证在处理j的时候，j-1的状态没有被当前x的其他因数更新过。 这样，对于每个x来说，它能贡献的j的数目是其所有的因数，每个因数j对应的子序列数目是之前的j-1的数目。因此，通过这种方式，动态地维护了每个j的可能数目。 最终，答案就是所有dp[1] + dp[2] + ... + dp[n]的总和，模上mod的值。 现在，再来看代码的结构： - 初始化dp数组，其中dp[0] =1，其他初始为0。 - 对于每个元素x，找到它的所有因数，并按从大到小排序。 - 对每个因数j，按排序后的顺序，执行dp[j] += dp[j-1]，并取模。 这样处理每个元素x，就能逐步构建出各个长度的合法子序列数目。 举个例子，假设输入的n=3，数组是1,2,3。 处理第一个元素x=1： 因数有1。排序后还是1。 处理j=1：dp[1] += dp[0] → dp[1]=1. 此时，dp数组为：[1,1,0,0]. 处理第二个元素x=2： 因数有1,2。排序后是2,1. 处理j=2：dp[2] += dp[1] → 0 +1=1. 处理j=1：dp[1] += dp[0] →1+1=2. 现在dp数组：[1,2,1,0]. 处理第三个元素x=3： 因数有1,3。排序后3,1. 处理j=3：dp[3] += dp[2] →0 +1=1. 处理j=1：dp[1] +=1 →2+1=3. 现在dp数组是：[1,3,1,1]. 总和是3+1+1=5。但原题中的样例输出是13，这说明可能这个例子并不符合样例情况。所以可能原题中的样例输入是更大的数组，或者不同的数值。 可能原题的样例输入是n=5，数组中的元素有很多因数的情况。例如，假设输入是n=5，数组中的元素都是1，那么每个元素的因数是1。处理每个元素时，j=1的处理会导致dp[1]每次加1，然后可能dp[1]会变为5。但其他长度的情况可能如： 每个元素x=1的因数是1，所以处理j=1。每次处理x=1时，dp[1] += dp[0]（即每次加1）。所以五个元素处理完后，dp[1]=5，其他dp[j]可能未被更新。总共有5种长度为1的子序列，其他长度没有。所以总和是5。但原题中的样例输出是13，说明可能输入的数组中的元素可以形成较多的子序列组合。 现在，回到问题本身，用户希望详细讲解这个问题的解法，尤其是动态规划的思路和优化方法。因此，我需要将整个思路逐步分解，帮助用户理解。 首先，动态规划的状态定义是关键。原来的二维状态被优化为一维数组，通过逆序处理因数来避免覆盖问题。对于每个元素x，找出所有因数j，这些j是可能的子序列长度，x可以作为第j个元素的条件是x能被j整除。因此，j必须是x的因数。 然后，将这些因数从大到小处理，确保在更新较大的j时，较小的j还没被处理，这样在更新j时，dp[j-1]的值还是处理当前元素之前的旧值。例如，在处理j=2时，如果x的因数还包括1，那么处理j=2的时候，j-1=1还没有被当前元素处理过，所以dp[1]的值是之前的状态，这样就能正确地进行转移。 这样，每个元素x的处理都会对各个可能的j长度的子序列数目进行更新，从而累积答案。 总结来说，这个问题的解法是动态规划，通过状态转移的方式，逐步累积每个长度j的合法子序列数目。优化空间的方法是使用滚动数组，并且处理因数的顺序是关键。</think>好的，我来为你详细讲解这道题目的解法思路。我们将从问题分析、动态规划定义、优化思路到代码实现逐步展开。 --- ### **问题分析** 题目要求找出序列中所有满足特定条件的子序列个数。条件为：对于子序列的第$i$个元素，其值必须能被$i$整除（$i$从1开始）。最终结果需要对$10^9+7$取模。 例如，子序列$[a_2, a_5, a_7]$的长度为3，需满足： - $a_2 \% 1 = 0$（任何数都能被1整除） - $a_5 \% 2 = 0$ - $a_7 \% 3 = 0$ --- ### **暴力动态规划思路** 设状态$dp[i][j]$表示前$i$个元素中，长度为$j$的合法子序列个数。状态转移方程为： $$ dp[i][j] = dp[i-1][j] + \begin{cases} dp[i-1][j-1], & \text{if } a[i] \% j = 0 \\ 0, & \text{otherwise} \end{cases} $$ - **不选第$i$个元素**：继承$dp[i-1][j]$的值。 - **选第$i$个元素**：当$a[i]$能被$j$整除时，可以接在长度为$j-1$的子序列后面。 但直接实现会面临$O(n^2)$的空间复杂度问题，当$n=10^5$时，无法处理。 --- ### **空间优化：滚动数组** 观察发现，$dp[i][j]$只依赖于$dp[i-1][j]$和$dp[i-1][j-1]$。因此可以优化为一维数组，并从后向前更新（避免覆盖未处理的状态）： - 用$dp[j]$表示当前处理到某个元素时，长度为$j$的合法子序列个数。 - **倒序更新**：从大到小遍历$j$，确保在更新$dp[j]$时，$dp[j-1]$未被当前元素修改。 --- ### **核心优化：因数分解** 对于每个元素$a[i]$，只有当$j$是$a[i]$的因数时，$a[i]$才能作为长度为$j$的子序列的最后一个元素。因此： 1. **找出$a[i]$的所有因数**（例如，$a[i]=6$的因数为$\{1,2,3,6\}$）。 2. **按从大到小排序因数**：确保在更新$dp[j]$时，$dp[j-1]$是之前的状态。 例如，处理$a[i]=6$的因数时，按$6→3→2→1$的顺序更新，保证大因数先处理。 --- ### **算法步骤** 1. **初始化**：$dp[0] = 1$（空序列的方案数为1）。 2. **遍历每个元素**： - 找出当前元素的所有因数，并按从大到小排序。 - 对每个因数$j$，执行$dp[j] = (dp[j] + dp[j-1]) \% \text{mod}$。 3. **统计答案**：累加$dp[1] + dp[2] + \dots + dp[n]$。 --- ### **代码解析** ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5, mod = 1e9 + 7; long long dp[N], factors[N]; int main() { int n; cin >> n; dp[0] = 1; // 初始状态：空序列 for (int i = 1; i <= n; i++) { int x, cnt = 0; cin >> x; // 找出x的所有因数 for (int j = 1; j * j <= x; j++) { if (x % j == 0) { factors[++cnt] = j; if (x / j != j) factors[++cnt] = x / j; } } // 按从大到小排序因数 sort(factors + 1, factors + cnt + 1, greater<int>()); // 动态规划更新 for (int j = 1; j <= cnt; j++) { int len = factors[j]; if (len > n) continue; // 超过序列长度则跳过 dp[len] = (dp[len] + dp[len - 1]) % mod; } } // 统计所有长度的合法子序列数 long long ans = 0; for (int i = 1; i <= n; i++) ans = (ans + dp[i]) % mod; cout << ans << endl; return 0; } ``` --- ### **关键点解释** 1. **因数分解**：快速找到所有因数，确保时间复杂度为$O(\sqrt{x})$。 2. **倒序更新**：保证在更新大因数时，小因数还未被处理，避免覆盖。 3. **初始化$dp[0]=1$**：空序列是唯一长度为0的方案，用于推导后续状态。 --- ### **复杂度分析** - **时间复杂度**：$O(n \sqrt{x})$，其中$x$为元素的最大值。 - **空间复杂度**：$O(n)$，使用一维$dp$数组。 --- ### **示例说明** 假设输入为$n=3$，序列为$[2, 2, 2]$： 1. 处理第一个2： - 因数为$\{1,2\}$，排序为$2,1$。 - 更新$dp[2] += dp[1]$（此时$dp[1]=0$，无效）。 - 更新$dp[1] += dp[0]$ → $dp[1]=1$。 2. 处理第二个2： - 更新$dp[2] += dp[1]=1$ → $dp[2]=1$。 - 更新$dp[1] +=1$ → $dp[1]=2$。 3. 处理第三个2： - 更新$dp[2] += dp[1]=2$ → $dp[2]=3$。 - 更新$dp[1] +=1$ → $dp[1]=3$。 4. 最终答案：$dp[1] + dp[2] + dp[3] = 3 + 3 + 0 = 6$。 --- 通过这种动态规划方法，我们高效地统计了所有可能的子序列数，避免了暴力枚举的指数级复杂度。希望这篇讲解能帮助你理解这道题的解法！