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;
}