题解：CF2069C Beautiful Sequence

CF2069C

Statement

我们定义一个序列为美丽的当它满足：

序列长度至少为 $3$ 。
除第一个元素外，每个元素左侧都有一个小于它的元素。
除最后一个元素外，每个元素右侧都有一个大于它的元素。

给定长度

n

的数组

a

，求

a

的所有子序列中美丽的子序列的个数，答案对

998244353

取模。

n \leq 2 \times 10^5,a_i \in [1,3]

。

Solution

我们拥有人类智慧。

看到

a_i \in [1,3]

我们试试考虑算贡献，记产生正贡献 / 负贡献分别为

G,F

。

1

开头

3

结尾中间全是

2

的子序列满足条件。

对于 $a_i = 2$ ，它对于左右两边的 $1,3$ 均有贡献，可以插在中间，所以更新 $G \leftarrow G \times 2$ 。
对于 $a_i = 3$ ，它对于左边的 $1,2$ 有贡献，但是右边毫无贡献，只能作为末尾，更新 $G \leftarrow G + 1,F \leftarrow F + 1$ 。
对于 $a_i = 1$ ，同理只能作为开头，这时更新答案 $ans \leftarrow ans + G - F$ 。

Code

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 33, MOD = 998244353;
int T, n, A[MAXN];

signed main() {
	scanf ("%lld", &T);
	while (T --) {
		scanf ("%lld", &n);
		for (int i = 1; i <= n; i ++)
			scanf ("%lld", &A[i]);
		int F = 0, G = 0, Ans = 0;
		for (int i = n; i; i --) {
			if (A[i] == 2) {
				G = (G << 1) % MOD;
			} else if (A[i] == 3) {
				F ++, G ++;
			} else {
				Ans = (Ans + G - F + MOD) % MOD;
			}
		}
		printf ("%lld\n", Ans);
	}	
	return 0;
}

题解：CF2069C Beautiful Sequence

文章操作

Statement

Solution

Code

相关推荐

评论

题解：CF2069C Beautiful Sequence