P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳 题解

· · 题解

解法分析

贪心。我们分正负数两种情况分析：

对于正数。因为可以有空段，那么把所有正数都放最后一段就行了。利用初中简单整式乘法知识推一下每轮结果是如何增加的：首先由完全平方公式 (a+b)^2=a^2+2ab+b^2 可知 (a+1)^2=a^2+2a+1，那么 a_1,a_2,a_3,\ldots,a_n 同时加上 1 后的平方和便为：

{\sum a_i^2+2\times \sum a_i}+n

代码实现中用变量 q 记录上一轮的结果（\sum a_i^2），所有正数之和为 psum（\sum a_i），每一轮 q\gets q+psum\times 2+n,\ psum\gets psum+n 即可。

对于负数。首先想让平方和大就是要让绝对值大，那么在某个负数加上段数（就是把它放在最后一段会给它加上的数）后的绝对值大于它加 1（即放在第一段）的绝对值之前，都要把它放在第一段。换言之，对于一个负数 a，在 \left | a+m \right | >\left | a+1 \right | 之前，都要让它在第一段。那么当它满足放在最后一段的条件后，就可以愉快地让它加入正数之列了，可以再用变量 b 记录第一个正数的位置，每次有新数加入时 b\gets b-1,\ n\gets n+1,\ psum\gets psum+a+m,\ q\gets q+\Delta（\Delta =(a+m)^2-(a+1)^2，即答案差）即可。

代码

先算出第一轮（m=1）中各变量的值，后面循环求。
读写函数定义已省略。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mod 998244353

ll a[1000005];

int main() {
  int n = read(), k = read(), b = 0;
  ll q = 0, ans = 0, psum = 0, del;
  for (int i = 0; i < n; ++i)
    a[i] = read(), b += a[i] < 0, q = (q + (a[i] + 1) * (a[i] + 1) % mod) % mod;
  ans += q;
  for (int i = b; i < n; ++i) psum = (psum + a[i] + 1 % mod) % mod;
  n = n - b;
  for (int m = 2; m <= k; ++m) {
    ans = (ans + (q = (q + psum * 2 % mod + n) % mod)) % mod,
    psum = (psum + n) % mod;
    while (b > 0 && a[b - 1] + m > abs(a[b - 1] + 1)) {
      --b, ++n;
      del = (a[b] + m) * (a[b] + m) % mod - (a[b] + 1) * (a[b] + 1) % mod;
      ans = (ans + del) % mod, q = (q + del) % mod, psum = (psum + (a[b] + m) % mod) % mod;
    }
  }
  write(ans);
  fls();
  return 0;
}