NSOqwq

题解 CF1061C【Multiplicity】

题解 CF1061C【Multiplicity】


题目大意

在长度为 $n$ 的数列 $a$ 中,找出一个非空子序列 $b$,使得 $b$ 中每一个元素的值都能被其对应在 $b$ 中的下标整除。求这样的 $b$ 的个数。


基础分析

假如我们不看数据范围,很容易直接想到一种最简单的 dp。

设 $f(x,y)$ 为前 $x$ 个数里选 $y$ 个数的方案数,显然:

$$ f(x,y) = \begin{cases} f(x-1, y) + f(x-1,y-1) & y \mid a_x \\ f(x-1,y) & otherwise. \end{cases} $$

但是由于 $1 \le n \le 10^5$,这种做法的时间复杂度和空间复杂度都会瞬间爆炸,需要进行优化。


优化空间

很容易看出 dp 的第一维都是由 $x-1$ 推过来,于是可以滚动数组把这一维省略掉。省略后时间复杂度不变,核心代码如下:

f[0] = 1;
for (int x = 1; x <= n; ++x)
  for (int y = x; y >= 1; ++y)
    if (a[x] % y == 0)
      f[y] += f[y - 1];

注意: 以原来二维的 dp 方式,对于 $f(x,y)$ 的更改是不会影响 $f(x-1,y),f(x-1,y-1)$ 的。但现在,没有了第一维 $x$ 和 $x - 1$ 的区分,更改 $f(y)$ 的时候就会影响原来的 $f(y)$ 和 $f(y-1)$,导致计算错误。倒着枚举 $y$ 就不会出现这样的问题。


优化时间

整个算法时间复杂度最高的地方在哪里?发现一个个判断 $y$ 是否整除 $a_x$ 是很累的,时间复杂度达 $O(n)$。

可以发现,只有是 $a_x$ 的因数且小于等于 $x$ 的 $y$ 才需要进行特殊处理,而这类数其实占比很少,一个个判断很耗时间。

于是可以 $O(\sqrt n)$ 提前找出所有 $a_x$ 的因数,再对于 $a_x$ 所有小于等于 $x$ 的因数 $y$ 进行 dp 即可。

输入的时候,把 $a_x$ 的所有因数一一存好,并从大到小排序,等到 dp 的时候可以直接用。当然,也可以在 dp 的第一层循环内对于 $a_x$ 分解因数,两者是一样的。

这一部分可以使用 std::vector 来实现。

注意,仍需从大到小遍历 $y$。


代码实现

signed main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int a = read();
        for (int p = 1; p * p <= a; ++p)
            if (a % p == 0) {
                factors[i].push_back(p);
                if (p * p != a)
                    factors[i].push_back(a / p);
            }
        std::sort(factors[i].rbegin(), factors[i].rend()); // 利用 vector 的 rbegin, rend 从大到小排序。
    }
    f[0] = 1;
    for (int x = 1; x <= n; ++x)
        for (int y : factors[x]) {
            if (y > x) continue; // y <= x 时才需 dp。
            f[y] = (f[y] + f[y - 1]) % MOD;
        }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = (ans + f[i]) % MOD;
    printf("%lld\n", ans);
    return 0;
}

2021-07-27 23:12:47 in 题解