Multiplicity

Created by LXC on Tue May 30 09:23:32 2023

https://codeforces.com/problemset/problem/1061/C

ranting: 1700

tag: data structures, dp, implementation, math, number theory

problem

给出长度为n的数组a，现在从中选出一个子序列b，如果$b_i \bmod i = 0$则称b为好数组。

请问能够选出多少个好数组。

solution

动态规划。

考虑每个前缀形成的好数组长度。
定义$f_{i,j}$为前i个数形成了长度为j的好数组的个数。
那么对于第i个数$a_i$：

• 若$a_i$不是是j的倍数，那么不能作为长度为j的好数组的最后一个数，长度为j的好数组只能由前i-1个数构造，所以有$f_{i,j} = f_{i-1,j}$
• 若$a_i$是j的倍数，那么既可以选择也可以不选择$a_i$作为长度为j的好数组的最后一个数，所以有$f_{i,j} = f_{i-1, j} + f_{i-1,j-1}$。

显然这样的空间复杂度是$O(n\sqrt n)$，本题时间给足3s，但是空间只有256m。
我们需要考虑空间优化。由于状态转移只涉及$f_{i-1,?}$和$f_{i,?}$所以可以用滚动数组减少一维空间。

对于状态转移$f_{i,?}$只需考虑从$f_{i-1,j}$转移来，其中$j$为$a_i$的因子，共$O(\sqrt a_i)$个。所以总时间复杂度$O(n\sqrt {\max \limits_{i=1}^{n} a_i})$，由于使用了滚动数组，我们需要由大到小的枚举因子。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1000005
#define MOD 1000000007
using namespace std;

int a[N];
int f[N];

void sol() {
    f[0] = 1;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x, j;
        cin >> x;
        for (j = 1; j * j < x; j++) {
            if (x % j == 0)
                f[x / j] += f[x / j - 1], f[x / j] %= MOD;
        }
        if (j * j > x)
            j--;
        for (; j > 0; j--) {
            if (x % j == 0)
                f[j] += f[j - 1], f[j] %= MOD;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += f[i];
        ans %= MOD;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}