The Battle of Chibi
题面
给定一个长度为 \(N\) 的序列 \(A\) ，求 \(A\) 有多少个长度为 \(M\) 的严格递增子序列
\(1 \le M \le N \le 1000,\ |A_i| \le 10^9\)
答案对 \(10^9\) 取模
题解
设 \(f(i,j)\) 表示以 \(a_j\) 为结尾的长度为 \(i\) 的严格递增子序列的数量，初始 \(f(0, 0) = 1\) ，目标：\(\sum f(m,j)\)
转移
\[f(i,j) = \sum_{0 \le k < j, a_k < a_j} f(i - 1, k)
\]
这个要是直接做的话时间复杂度为 \(O(N^2)\)
所以我们要想办法优化一下，因为是所有满足 \(0 \le k < j, a_k<a_j\) 的 \(k\) ，所以可以用树状数组，\(t(a_k) = f(i - 1, k)\) ，然后在树状数组中查询即可
但是因为 \(A_i\) 的范围太大，树状数组存不下，所以要提前离散化一下，然后就可以 \(O(n \log n)\) 的进行一阶段的转移
总时间复杂度为 \(O(mn \log n)\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 3e3 + 10;
const int mod = 1e9 + 7;int T, n, m, mn;
int a[N], b[N], val[N];
int t[N], f[N][N];void add (int x, int d) {while (x <= mn) {t[x] = (t[x] + d) % mod;x += x & -x;}
}int ask (int x) {int res = 0;while (x) {res = (res + t[x]) % mod;x -= x & -x;}return res;
}void solve (int id) {cin >> n >> m;mn = n;for (int i = 1; i <= n; i ++) {cin >> a[i];b[i] = a[i];}a[0] = -2e9;b[ ++ mn] = a[0];sort (b + 1, b + 1 + mn);mn = unique (b + 1, b + 1 + mn) - 1 - b;for (int i = 0; i <= n; i ++) {val[i] = lower_bound (b + 1, b + 1 + mn, a[i]) - b;}memset (f, 0, sizeof f);f[0][0] = 1;for (int i = 1; i <= m; i ++) {memset (t, 0, sizeof t);add (val[0], f[i - 1][0]);for (int j = 1; j <= n; j ++) {f[i][j] = ask (val[j] - 1);add (val[j], f[i - 1][j]);}}int res = 0;for (int i = 1; i <= n; i ++) {res = (res + f[m][i]) % mod;}printf ("Case #%d: %d\n", id, res);}int main () {cin >> T;for (int i = 1; i <= T; i ++) {solve (i);}return 0;
}