【状态机DP、权值树状数组】ABC439F
WanderOvO
·
·
题解
【状态机DP、权值树状数组】ABC439F
原题链接
简要题意
给你一个 1 到 N 的排列 P，求其好子序列的个数。
一个序列 a_{1...n} 是好的，当且仅当其峰的个数大于谷的个数，峰就是满足 2 \le i \le n - 1 且 a_i > a_{i - 1},a_i > a_{i + 1} 的 i 的个数，谷就是满足 2 \le i \le n - 1 且 a_i < a_{i - 1},a_i < a_{i + 1} 的 i 的个数。
## 思路
这种计数题要么 DP 要么推式子，本题把排列 $P$ 通过输入给出来了，所以会倾向于往 DP 上思考。
我们首先应该发现一个事情，$P$ 的任何一个子序列，其峰和谷的个数至多差 $1$。
为什么呢，我们考虑序列的升降趋势，发现只有下面四种情况：
- **升降升降...升**：由于每个“升降”的改变点会带来一个峰，每个“降升”的改变点会带来一个谷，所以这种情况下峰的个数等于谷的个数。
- **升降升降...升降**：分析可知峰的个数比谷的个数恰好多一个。
- **降升降升...降**：和第一种情况一样，峰的个数等于谷的个数。
- **降升降升...降升**：分析可知峰的个数比谷的个数恰好少一个。
- **单点**：**这个很容易忘记**！因为为了形成升或者降的趋势，**至少是有两个数才行**，而只有一个数时是没有趋势的，所以这种情况要单列出来。
因此，这道题其实就是计数**第二种情况的子序列有多少**。
我们考虑设：
- $dp[i][0]$ 为以第 $i$ 个数结尾的**只有一个数**的序列个数。
- $dp[i][1]$ 为以第 $i$ 个数结尾的，趋势是**升降升降...升**的序列个数。
- $dp[i][2]$ 为以第 $i$ 个数结尾的，趋势是**升降升降...升降**的序列的个数。
对于 $dp[i][0]$：
- $dp[i][0] = 1$。
对于 $dp[i][1]$：
- $dp[i][1] += dp[j][0]$，其中 $p[j] < p[i]$。
- $dp[i][1] += dp[j][1]$，其中 $p[j] < p[i]$。
- $dp[i][1] += dp[j][2]$，其中 $p[j] < p[i]$。
对于 $dp[i][2]$：
- 由于**先升了才能降**，所以单点序列 $dp[i][0]$ 不能转移过来。
- $dp[i][2] += dp[j][1]$，其中 $p[j] > p[i]$。
- $dp[i][2] += dp[j][2]$，其中 $p[j] > p[i]$。
显然这个转移可以用权值树状数组进行优化，我们开 3 棵树状数组，分别维护 $dp[i][0]$ 、$dp[i][1]$ 和 $dp[i][2]$ 的和即可。
实现时注意取模，以及涉及到取模减法的话记得最后把答案调整成非负数。
## 代码
```cpp
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
const int mod = 998244353;
struct Fenwick {
LL tr[N], n;
int lowbit(int x) {
return x & -x;
}
void add(int pos, LL x) {
while (pos <= n) {
tr[pos] += x;
tr[pos] %= mod;
pos += lowbit(pos);
}
}
LL query(int pos) {
LL res = 0;
while (pos > 0) {
res += tr[pos];
res %= mod;
pos -= lowbit(pos);
}
return res;
}
void init(int sz) {
n = sz;
for (int i = 0; i <= n; i++) {
tr[i] = 0;
}
}
void clear() {
for (int i = 0; i <= n; i++) {
tr[i] = 0;
}
}
};
Fenwick fen0, fen1, fen2;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
LL res = 0;
fen0.init(n + 2);
fen1.init(n + 2);
fen2.init(n + 2);
vector<vector<LL>> dp(n + 2, vector<LL>(2, 0));
for (int i = 1; i <= n; i++) {
LL down_cnt = 0, up_cnt = 0;
up_cnt += fen0.query(a[i] - 1) + fen1.query(a[i] - 1) + fen2.query(a[i] - 1);
down_cnt += fen1.query(n) - fen1.query(a[i])
+ fen2.query(n) - fen2.query(a[i]);
up_cnt %= mod;
down_cnt %= mod;
dp[i][0] = 1;
dp[i][1] = up_cnt;
dp[i][2] = down_cnt;
fen0.add(a[i], dp[i][0]);
fen1.add(a[i], dp[i][1]);
fen2.add(a[i], dp[i][2]);
}
for (int i = 1; i <= n; i++) {
res += dp[i][2];
res %= mod;
}
res = (res % mod + mod) % mod;
cout << res << "\n";
}
int main() {
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
```
## Bonus
通过上面的分析，我们其实注意到一个事情：**一个序列（长度不小于 $4$）是好的，当且仅当序列开头俩元素递增，结尾俩元素递减**。
假如题目**改成**问有多少个 $1$ 到 $n$ 的排列 $P$ 是好的，等价于只要考虑构造最开始 $2$ 个数递增，最后 $2$ 个数递减，中间随便排的方案了（$n \ge 4$），似乎是 $C(n, 4) \times C(4, 2) \times (n - 4)!$，化简一下就是 $\frac{n!}{4}$。
特判更小的情况即可解决 $n \le 3$ 。