NC 54585 DP + BIT

题意

传送门 NC 54585

题解

$dp[i][j]$ 代表以 $a[i]$ 结尾长度为 $j$ 的子序列，则有递推式 $$dp[i][j]=\sum _{i^{\prime }<i且a[i^{\prime }]<a[i]}dp[i^{\prime }][j-1]$$ $BIT[k]$ 以 $a[i]$ 为索引，维护长度为 $k$ 的子序列的数量和。

#include <bits/stdc++.h> using namespace std; #define maxn 500005 #define maxk 12 typedef long long ll; const int mod = 998244353; int n, k, a[maxn], dp[maxk], bit[maxn][maxk]; void compress(int *x, int n) { vector<int> xs(n); for (int i = 0; i < n; i++) { xs[i] = x[i]; } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int i = 0; i < n; i++) { x[i] = 1 + lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin(); } } void add(int i, int j, int x) { while (i <= n) { bit[i][j] = (bit[i][j] + x) % mod; i += i & -i; } } int sum(int i, int j) { int s = 0; while (i > 0) { s = (s + bit[i][j]) % mod; i -= i & -i; } return s; } int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%d", a + i); } compress(a, n); int res = 0; for (int i = 0; i < n; i++) { dp[1] = 1; for (int j = 2; j <= k; j++) { dp[j] = sum(a[i] - 1, j - 1); } for (int j = 1; j < k; j++) { add(a[i], j, dp[j]); } res = (res + dp[k]) % mod; } printf("%d\n", res); return 0; }