打 ABC 遇到的一类题型，感觉相似性还挺大的，遂整理。
子序列 dp，即统计一类子序列的数量，要求不重复并满足题目中的限制条件。
暴力统计通常是 \(O(N ^ 2)\) 的可以通过 前缀和优化 达到 \(O(N)\)。但这不是难点所在。
这类 dp 有一个非常重要的前置贪心。为了保证我们统计的子序列不重复，我们人为规定需要的数字要尽早拿走，这样就可以确保对于一个数组，我们想取的一种子序列有且只有一种取法。
比如数组 (1, 2, 3, 2)，如果我们想取子序列 (1, 2)，通过我们的人为规定，唯一合法的就是拿下标为 1 和 2 的数，拿下标为 1 和 4 的数字是不合法的。
了解这个前置知识就可以看模板题了。
模板题 Leetcode 940. 不同的子序列 II
public:int distinctSubseqII(string s) {const int mod = 1e9 + 7;int n = s.size();s = "$" + s; vector<long long> dp(n + 1, 0), sum(n + 1, 0);vector<int> pos(27, 0);dp[0] = sum[0] = 1;for(int i = 1; i <= n; ++i) {if(pos[s[i] - 'a'] == 0) {dp[i] = sum[i - 1];}else {dp[i] = (sum[i - 1] - sum[pos[s[i] - 'a'] - 1] + mod) % mod;}sum[i] = (sum[i - 1] + dp[i]) % mod;pos[s[i] - 'a'] = i;}return (int)(sum[n] - 1 + mod) % mod;}
};
设 \(dp_i\) 代表以 \(a_i\) 结尾的合法子序列的个数。更平常的说，代表的是依据我们之前看见一个拿一个的贪心策略，以 \(a_i\) 结尾的子序列数量。
考虑如何转移。如果转移的位置在上一个与 \(a_i\) 相等的数字之前，那么就违反了见一个拿一个的策略。因此答案应该是 \(\sum _{j = lst} ^ {i - 1} dp_j\)，\(lst\) 代表上一个 \(a_i\) 的位置。在更新的时候顺便维护前缀和即可。
ABC 446G
这个其实差不多，两个变化的地方，一个是不允许连续相同块出现，一个是每次必须要组成一个块。所以对于 \(a_i\) 答案变成了第 \(i - a_i\) 个和第 \(i - a_i + 1\) 个 \(a_i\) 之间的 \(dp\) 和。由于不允许连续，实现的时候要把左边界往后挪一位。
#include <bits/stdc++.h>
#define pb(x) push_back(x)
#define int long long
#define ull unsigned long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define rep_(i, a, b) for(int i = a; i >= b; --i)
using namespace std;
namespace FYH {constexpr int N = 5e5 + 5, mod = 998244353;int n, x;void main() {cin >> n;vector<int> dp(n + 1, 0), sum(n + 1, 0), cnt(n + 1, 0);vector<vector<int>> pos(n + 1);dp[0] = sum[0] = 1;rep(i, 1, n) {cin >> x;if(x > n) {continue;}pos[x].push_back(i);cnt[x]++;if(cnt[x] > x) {dp[i] = (sum[pos[x][cnt[x] - x] - 1] - sum[pos[x][cnt[x] - x - 1]] + mod) % mod;}else if(cnt[x] == x) {dp[i] = sum[pos[x][0] - 1];}sum[i] = (sum[i - 1] + dp[i]) % mod;}cout << (sum[n] - 1 + mod) % mod;}
}
signed main() {ios :: sync_with_stdio(0), cin.tie(0);int t = 1;while(t--) {FYH :: main();}return 0;
}