CF1061C Multiplicity

tZEROちゃん · 2022-07-25 18:17:49 · 题解

Update：上传成 wa 的代码了，已修改。

dp 题。

设 dp_{i,j} 表示从 a 中前 i 个数中选取一个长度为 j 的符合要求的子序列的数量，最终答案显然是 \sum dp_{n,i}。

当 a_i 是 j 的倍数时，显然 dp_{i, j} = dp_{i - 1,j} + dp_{i - 1,j - 1}；当 a_i 不是 j 的倍数时，dp_{i, j} = dp_{i - 1,j}。

所以状态转移方程是

但是注意到这个空间和时间都会寄，所以考虑优化。

我们注意到 dp_{i, j} 只与 dp_{i - 1, j} 有关，所以前面那些就不用保存了。

还可以注意到，dp_j 会变化，当且仅当 j\ |\ a_i，而我们可以在 \mathcal O(\sqrt x) 的时间复杂度内找到 x 的因子。

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define pb push_back

#define rep(i, l, r) for (auto i = (l); i <= (r); ++i) 

const int N = 1e6 + 5,
          mod = 1e9 + 7;
LL a[N], dp[N];

int main() {
  LL n; cin >> n;
  dp[0] = 1;
  rep (i, 1, n) {
    cin >> a[i];
    vector<LL> v;
    for (LL j = 1; j * j <= a[i]; ++j) {
      if (a[i] % j == 0) {
        v.push_back(j);
        if (j != a[i] / j) v.push_back(a[i] / j);
      }
    }
    sort(v.begin(), v.end(), greater<LL>());
    for (auto i : v) {
    //  (dp[i] += dp[i - 1]) %= mod;
      dp[i] += dp[i - 1]; dp[i] %= mod;
    }
  }
  LL ans = 0;
  rep (i, 1, n) {
    // (ans += dp[i]) %= mod;
    ans += dp[i]; ans %= mod;
  }

  printf("%lld", ans % mod);
}