学习算法 题解

· · 题解

Subtask 2

朴素 DP，设 f(i,j,k) 为第 i 天，最后学的是第 j 种算法，连续学了 k 天。

\begin{aligned} f(i,c,1)&=\sum_{j\in\complement_{[1,m]}\{i\}} \sum_{k=1}^{a_j} f(i-1,j,k)\\ f(i,c,k)&=f(i-1,c,k-1)\\ \end{aligned}

时空复杂度 O(n^2m^2),O(n^2m)。

re(i, m) f[1][i][1] = 1;
rep(i, 2, n) {
  re(c, m) {
    re(j, m) {
      if (j == c) continue;
      re(k, a[j]) f[i][c][1] += f[i - 1][j][k], umod(f[i][c][1]);
    }
    rep(k, 2, a[c]) f[i][c][k] = f[i - 1][c][k - 1];
  }
}
re(i, n) { re(j, a[i]) ans += f[n][i][j], umod(ans); }

Subtask 3

试着把第三维压掉：

f(i,c)=\sum_{j\in\complement_{[1,m]}\{i\}} \sum_{k=\max\{1,i-a_j\}}^{i-1} f(k,j)

时空复杂度 O(n^2m^2),O(nm)。

re(i, m) f[1][i] = 1;
rep(i, 2, n) {
  re(c, m) {
    re(j, m) {
      if (j == c) continue;
      rep(k, max(1, i - a[j]), i - 1) f[i][c] += f[k][j], umod(f[i][c]);
    }
  }
}
re(i, m) {
  rep(j, n - a[i] + 1, n) { ans += f[j][i], umod(ans); }
}

再加一个用来辅助 f 的 g：

\begin{aligned} g(i,c)&=\sum_{j=\max\{1,i-a_c\}}^{i-1}f(j,c)=g(i-1,c)+f(i-1,c)-f(i-a_c-1,c)\\ f(i,c)&=\sum_{j\in\complement_{[1,m]}\{i\}} g(i,j) \end{aligned}

时空复杂度 O(nm^2),O(nm)。

re(i, m) f[1][i] = 1;
rep(i, 2, n + 1) {
  re(c, m) {
    g[i][c] = g[i - 1][c] + f[i - 1][c], umod(g[i][c]);
    if (i - a[c] - 1 >= 1) g[i][c] -= f[i - a[c] - 1][c], dmod(g[i][c]);
  }
  if (i != n + 1) {
    re(c, m) {
      re(j, m) {
        if (j == c) continue;
        f[i][c] += g[i][j], umod(f[i][c]);
      }
    }
  }
}
re(i, m) ans += g[n + 1][i], umod(ans);

Subtask 5

在 subtask 3 的基础上再加一个 h：

\begin{aligned} g(i,c)&=g(i-1,c)+f(i-1,c)-f(i-a_c-1,c)\\ h(i)&=\sum_{j=1}^m g(i,j)\\ f(i,c)&=h(i)- g(i,c) \end{aligned}

时空复杂度 O(nm),O(nm)。

re(i, m) f[1][i] = 1;
rep(i, 2, n + 1) {
  re(c, m) {
    g[i][c] = g[i - 1][c] + f[i - 1][c], umod(g[i][c]);
    if (i - a[c] - 1 >= 1) g[i][c] -= f[i - a[c] - 1][c], dmod(g[i][c]);
    h[i] += g[i][c], umod(h[i]);
  }
  if (i != n + 1) {
    re(c, m) f[i][c] = h[i] - g[i][c], dmod(f[i][c]);
  }
}
out(h[n + 1])('\n');

Subtask 6

在 subtask 5 的基础上利用滚动数组稍微压一下内存：

\begin{aligned} g(i\bmod 2,c)&=g((i\bmod 2) \oplus 1,c)+f(i-1,c)-f(i-a_c-1,c)\\ h&=\sum_{j=1}^m g(i\bmod 2,j)\\ f(i,c)&=h- g(i\bmod 2,c) \end{aligned}

时空复杂度 O(nm),O(nm)。

re (i, m)
  f[1][i] = 1;
rep (i, 2, n + 1) {
  int h = 0;
  re (c, m) {
    g[i & 1][c] = g[(i & 1) ^ 1][c] + f[i - 1][c], umod(g[i & 1][c]);
    if (i - a[c] - 1 >= 1) g[i & 1][c] -= f[i - a[c] - 1][c], dmod(g[i & 1][c]);
    h += g[i & 1][c], umod(h);
  }
  if (i == n + 1) {
    out(h)('\n');
  } else {
    re (c, m)
      f[i][c] = h - g[i & 1][c], dmod(f[i][c]);
  }
}