Sol P12728

· · 题解

修改

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

子任务 1，2

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

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

这样做时间复杂度为 \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。

这样求答案也是 $\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$ 分！ ```cpp 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}$。 所有贡献之和即为答案，注意取模！ --- 修改过后的核心部分： ```cpp 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); } ``` [完整代码提交记录搓这里。](https://www.luogu.com.cn/record/220109822) 最后 --- ~~求通过并无耻地求赞。~~