CF1421E Swedish Heroes

个人觉得挺妙的一个结论题。

首先不难发现每个数对答案的贡献是 \(a_i\) 或者 \(-a_i\)。

那么系数的序列应该有两个性质：必须存在两个相同的系数相邻。设有 \(p\) 个减号，\(q\) 个加号，满足 \(2p+q \equiv 1 \pmod{3}\)。

证明后面再写。

那么知道这个性质，考虑记 \(dp_{i,j,0/1,0/1}\) 表示第 \(i\) 位，模 \(3\) 的余数，这一位的系数，是否存在两个相同的系数相邻的最大值。

时间复杂度 \(O(n)\)。

注意要考虑到 +-+-+-... 或者 -+-+-+... 这类情况是不合法的。

结论的证明：

对于 \(n \in [1,3]\) 结论显然正确。

对于 \(n \geq 4\)，考虑合并之后 \(p'=q+1,q'=p\)。

那么就有 \(2(2p'+q')=3q+5\)。

显然 \(3q+5 \equiv 2 \pmod{3}\)，所以 \(2p+q \equiv 1 \pmod{3}\)。

#include 
#define reg register
#define ll long long
#define ull unsigned long long
#define rep(i,a,n) for(reg int (i)=(a);(i)<=(n);++(i))
#define per(i,a,n) for(reg int (i)=(a);(i)>=(n);(i)--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define debug(typ...) fprintf(stderr, typ)
using namespace std;
const int iINF=numeric_limits::max();
const ll lINF=numeric_limits::max();
int fastin() {
  reg int x = 0, ch = getchar(), f = 0;
  while(!isdigit(ch)) (ch == '-') && (f = 1), ch = getchar();
  while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
const int MAXN=2e5+10;
int n;
ll a[MAXN],dp[MAXN][3][2][2];
template
void checkmax(reg typ &x,reg typ y) {
  if(x