$T$筆測資，
每筆測資給一$N$項數列及一數字$K$，求長度介於$[1,K]$的相異遞增子序列數量$\mod 2^{61}-1$。
$T\le 8,N\le 10^5,K\le 70, 1\le a_i\le 10^9$
令$dp[i][j]$為結尾為$a_i$，且長度為$j$的遞增子序列數量，轉移式為：
$$dp[i][j] = \sum^{i}_{k=1} dp[k][j-1],\ a_k<a_i$$
以上轉移可用單點修改，求前綴和的資料結構來達到$\mathcal{O}(log n)$轉移。
將$a_i$當成index，$dp[i][j-1]$當成value，上述dp的轉移可視為求$1$到$a_i-1$的前綴和，但$a_i$範圍太大，需要先離散化。
且最後一筆會卡空間，因此必須將$j$那一維壓成滾動。
時間複雜度$\mathcal{O}(TNK)$，空間複雜度$\mathcal{O}(N)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
const ll mod = (1LL<<61)-1;
const int N = 1e5+25;
ll bit[N];
void modify(int p, ll val) {
for(; p<N; p+=p&-p)
bit[p] = (bit[p] + val) % mod;
}
ll sum(int p) {
ll res = 0;
for(; p; p-=p&-p)
res = (res + bit[p]) % mod;
return res;
}
signed main() {
EmiliaMyWife
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
vector<int> arr(n+1), v;
vector<vector<ll>> dp(2, vector<ll>(n+1));
for(int i = 1; i <= n; i++)
cin >> arr[i], v.push_back(arr[i]);
v.push_back(0);
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
for(int i = 0; i <= n; i++)
arr[i] = upper_bound(v.begin(), v.end(), arr[i])-v.begin();
dp[0][0] = 1;
ll ans = 0;
int now = 1, prv = 0;
for(int i = 1; i <= k; i++) {
memset(bit, 0, sizeof bit);
for(int j = 0; j <= n; j++)
dp[now][j] = 0;
for(int j = 1; j <= n; j++) {
modify(arr[j-1], dp[prv][j-1]);
dp[now][j] = sum(arr[j]-1);
ans = (ans + dp[now][j]) % mod;
}
swap(now, prv);
}
cout << ans << '\n';
}
return 0;
}
|