自动搬运

查看原文

来自洛谷，原作者为

	lcfollower 不 AK Div.2 & 3 不改签 | AT 不上蓝不改签（目前只有绿）。 | 不拿蓝钩不改签。 | 大号在 N 个月前已清关，误清的用这个号回关

搬运于2025-08-24 23:17:45，当前版本为作者最后更新于2025-06-10 21:03:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

修改

• $2025.7.31$：根据评论修改一处错误（自己懒得写对应部分分代码犯下了唐错误），并且顺带修改一点错别字和写错的值域范围。

---

这题其实一眼 DP，但是可能状态设计需要细想才能优化。

子任务 $1$，$2$

这里的 $a ,b$ 很小，$T = 1$。

于是我们设 $f_{i ,j, k}$ 为前 $i$ 个环，红色的和恰好为 $j$，蓝色的和恰好为 $k$ 的方案数。

• 边界条件：$f_{0 ,0 ,0} = 1$

• 状态转移：$f_{i ,j ,k} = f_{i - 1 ,j - i ,k} + f_{i - 1 ,j ,k - i}$。

• 其中，$f_{i - 1 ,j - i ,k}$ 表示第 $i$ 圈涂红的方案数，$f_{i - 1 ,j ,k - i}$ 表示第 $i$ 圈涂蓝的方案数。

• 注意边界！比如 $j \ge i$ 或 $k\ge i$ 才能转移之类的。

• 记 $s = \frac{(1 + i)i}{2}$，即前 $i$ 圈数值的和，又可以理解为红色与蓝色的和（正好涂满整个所有环）。

• 转移条件：$j + k = s$，即正好涂满。

这样做时间复杂度为 $\mathcal O(nV^2)$，其中 $n$ 为圈的个数，$V$ 为 $a$，$b$ 的值域（即 $5\times 10^4$）。

但是观察到，转移条件为 $j + k = s$，我们可以在 $[0,s]$ 枚举 $j$，然后通过 $k = s - j$ 求的 $k$。

这样的时间复杂度为 $\mathcal O(nV)$。

那么答案即为 $\sum\limits_{i = 1}^{n}\sum\limits_{j=0}^a [s-j\le b]\times f_{i,j,s-j}$。

其中，$[A]$ 表示 $A$ 成立，值为 $1$；否则为 $0$。

$s$，表示 $\frac{(1+i)i}{2}$，下文都这么表示，不再阐述。

这样求答案也是 $\mathcal O(nV)$ 的，足以通过两个子任务，总时间复杂度为 $\mathcal O(TnV)$，理论上来说可以做到 $90$！

这里埋了一个点，$n$ 的范围？

考虑到 $a+b\ge s$，不然整个圈都涂不满。

因为 $s = \frac{i(i+1)}{2}$，$a+b\le 10^5$。

所以 $s$ 约为 $\lfloor\sqrt{2\times 10^5}\rfloor = 447$，数组开 $450$ 包不会缺少圈数，更何况 $447$ 还是估大了。

但是过不了更高的分数是因为空间问题。

代码这里不放了，可以自己练练手。

空间优化

考虑到 $f_{i,j,k}$ 只有在 $j+k=s$ 时才能转移，那么我们能不能：

• 状态设计：$f_{i,j}$ 为前 $i$ 圈涂红的和恰好为 $j$，涂蓝的和恰好为 $s - j$ 的方案数。

这样明显是可以的！

那么：

• 边界条件：$f_{0 ,0} = 1$。

• 状态转移：$f_{i ,j} = f_{i - 1,j} + f_{i - 1 ,j - i}$。

• 其中，$f_{i - 1,j}$ 表示第 $i$ 圈涂蓝的方案数，$f_{i - 1 ,j - i}$ 表示第 $i$ 圈涂红的方案数。

• 注意边界！比如 $j\ge i$ 才能转移之类的。

这样空间复杂度变成了 $\mathcal O(nV)$！即为 $\mathcal O(V\sqrt{V})$，非常优秀！

于是我们拿到了 $90$ 分！

inline void solve (){
  int x = read () ,y = read () ,ans = 0;
  up (i ,1 ,450) {
    int s = (1 + i) * i / 2;
    up (j ,s - y ,x) ans += f[i][j] ,ans %= mod;
//在这个范围内可以保证 s - j <= y，可以自己解不等式试试。
  } writeln (ans);
} inline void init (){
  f[0][0] = 1;//边界条件。
  up (i ,1 ,450){
    int s = (1 + i) * i / 2;
    up (j ,0 ,50000){
      int k = s - j;
      if (k < 0) break;//蓝的不可能涂色，不用转移。
      if (j >= i) f[i][j] = (f[i - 1][j] + f[i - 1][j - i]) % mod;//这一圈可以涂红，也可以涂蓝。
      else f[i][j] = f[i - 1][j];//不然这一圈这能涂蓝。
    }
  }
}

正解

观察到我们的瓶颈在于 $\operatorname {solve}$ 中，考虑优化它。

我们发现这是一段和的形式，于是我们想到用前缀和，这样时间复杂度为 $\mathcal O(Tn)$ 了。

但是前缀和还有边界，现在我们记 $f'_{i,x} = \sum\limits_{j=1}^x f_{i,j}$：

• 首先要满足 $s-y\le x$，不然不能转移。

• $s - y \le 0$，那么贡献为 $f'_{i,x}$。

• 否则，贡献为 $f'_{i,x} - f'_{i,s-y-1}$。

所有贡献之和即为答案，注意取模！

---

修改过后的核心部分：

inline void solve (){
  int x = read () ,y = read () ,ans = 0;
  up (i ,1 ,450) {
    int s = (1 + i) * i / 2;
    int p = max (0ll ,s - y - 1);
    if (s - y > x) break;//不能转移，j 更大时肯定也不能转移。
    if (s - y <= 0) ans = (ans + f[i][x]) % mod;
    else ans += f[i][x] - f[i][p] + mod ,ans %= mod;//两种边界，防止 RE。
  } writeln (ans);
}

完整代码提交记录搓这里。

最后

求通过并无耻地求赞。