ARC128D

考虑我们直接\(dp\)。

那么需要快速的求出一段是否可以被消掉只剩两端。

我们可以考虑反过来做的。

我们知道如果全为\(abab\)型或者\(aa\)型则无法消掉

那么我们要前缀和，以及遇到\(aa\)则另起一套，否则我们记录最后一段\(abab\)的\(f\)和。

#include <bits/stdc++.h>

#define in read()

#define fi first

#define se second

#define pb push_back

#define rep(i, x, y) for(int i = (x); i <= (y); i++)

#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using pii = pair < int , int >;

using vec = vector < int >;

using veg = vector < pii >;

using ll = long long;

int read() {

    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();

    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;

}

const int N = 2e5 + 10;

const int mod = 998244353;

int a[N], s[N], n, f[N];

bool check(int l, int r) {

	if(r > l + 1 && a[l] == a[l + 1]) return 1;

	if(r > l + 1 && a[r] == a[r - 1]) return 1;

	return 0;

}

int pos[N];

int main() {

#ifndef ONLINE_JUDGE

    freopen("1.in","r",stdin);

#endif

    n = in; rep(i, 1, n) a[i] = in;

	int l = 1, ts = 0;

	rep(i, 1, n) {

		if(i == 1) f[i] = 1;

		if(a[i] == a[i - 1]) { l = i, ts = 0; f[i] = f[i - 1]; s[i] = (s[i - 1] + f[i]) % mod; continue; }

		f[i] = (f[i] + s[i - 1] - s[l - 1]) % mod;

		if(i - 3 >= l && a[i] == a[i - 2] && a[i - 1] == a[i - 3]) ts = (ts + f[i - 3]) % mod, f[i] = (f[i] + mod - ts) % mod; else ts = 0;

		f[i] = (f[i] + mod) % mod;

		s[i] = (s[i - 1] + f[i]) % mod;

		cerr << i << " " << l << " " << f[i] << endl;

	}

	printf("%d\n", f[n]); return 0;

}

巴特西

ARC128D

最新文章

热门文章