UVa 12983 The Battle of Chibi

问题重述给定一个长度为NNN的数组aaa求严格递增子序列的数量且子序列长度恰好为MMM。子序列必须保持原顺序。严格递增a[i]a[j]a[i] a[j]a[i]a[j]对于子序列中相邻元素成立。输出结果对109710^971097取模。思路分析111. 定义状态设dp[i][l]以 a[i] 结尾的长度为 l 的严格递增子序列的数量 dp[i][l] \text{以 } a[i] \text{ 结尾的长度为 } l \text{ 的严格递增子序列的数量}dp[i][l]以a[i]结尾的长度为l的严格递增子序列的数量那么最终答案是ans∑i1Ndp[i][M] ans \sum_{i1}^{N} dp[i][M]ansi1∑N​dp[i][M]222. 状态转移对于每个iii长度为lll的子序列可以由所有jij iji且a[j]a[i]a[j] a[i]a[j]a[i]的dp[j][l−1]dp[j][l-1]dp[j][l−1]转移而来dp[i][l]∑ji, a[j]a[i]dp[j][l−1] dp[i][l] \sum_{j i, \ a[j] a[i]} dp[j][l-1]dp[i][l]ji,a[j]a[i]∑​dp[j][l−1]初始条件dp[i][1]1每个元素本身构成一个长度为 1 的递增序列 dp[i][1] 1 \quad \text{每个元素本身构成一个长度为 } 1 \text{ 的递增序列}dp[i][1]1每个元素本身构成一个长度为1的递增序列333. 直接实现的复杂度直接三重循环枚举iii枚举lll枚举jjj是O(N2M)O(N^2 M)O(N2M)在N≤1000,M≤NN \leq 1000, M \leq NN≤1000,M≤N时可能达到10910^9109级别会超时。444. 优化我们需要快速计算∑ji, a[j]a[i]dp[j][l−1] \sum_{j i, \ a[j] a[i]} dp[j][l-1]ji,a[j]a[i]∑​dp[j][l−1]这是一个前缀和问题但a[i]a[i]a[i]的值很大最大10910^9109所以需要离散化。我们可以对每个长度lll维护一个树状数组 (Fenwick Tree\texttt{Fenwick Tree}Fenwick Tree)或线段树键是离散化后的a[i]a[i]a[i]值值是dp[i][l]dp[i][l]dp[i][l]。这样计算dp[i][l]dp[i][l]dp[i][l]时查询树状数组中[1,pos(a[i])−1][1, pos(a[i])-1][1,pos(a[i])−1]的区间和即所有值小于a[i]a[i]a[i]的dp[j][l−1]dp[j][l-1]dp[j][l−1]之和。然后更新树状数组在pos(a[i])pos(a[i])pos(a[i])位置加上dp[i][l]dp[i][l]dp[i][l]。这样复杂度降为O(T⋅M⋅Nlog⁡N) O(T \cdot M \cdot N \log N)O(T⋅M⋅NlogN)在T≤100,M≤N≤1000T \leq 100, M \leq N \leq 1000T≤100,M≤N≤1000时可行。5. 离散化因为aia_iai​很大但N≤1000N \leq 1000N≤1000我们可以对每个测试用例的aaa数组单独离散化。算法步骤读入TTT。对每个测试用例读入N,MN, MN,M和数组aaa。离散化aaa。初始化dp[N1][M1]dp[N1][M1]dp[N1][M1]为000且dp[i][1]1dp[i][1] 1dp[i][1]1。对l2l 2l2到MMM初始化树状数组大小为NNN。对i1i 1i1到NNN查询树状数组中[1,pos(a[i])−1][1, pos(a[i])-1][1,pos(a[i])−1]的和作为dp[i][l]dp[i][l]dp[i][l]。更新树状数组在pos(a[i])pos(a[i])pos(a[i])位置加上dp[i][l−1]dp[i][l-1]dp[i][l−1]注意这里加的是上一层的dp\texttt{dp}dp值。答案ans∑i1Ndp[i][M]\text{ans} \sum_{i1}^N dp[i][M]ans∑i1N​dp[i][M]取模输出。参考代码// The Battle of Chibi// UVa ID: 12983// Verdict: Accepted// Submission Date: 2025-10-16// UVa Run Time: 0.520s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includeiostream#includevector#includealgorithm#includecstringusingnamespacestd;constintMOD1000000007;constintMAXN1005;intT,N,M;inta[MAXN];intdp[MAXN][MAXN];// Fenwick TreeclassFenwick{intn;vectorintbit;public:Fenwick(intn):n(n),bit(n1,0){}voidupdate(intidx,intdelta){for(;idxn;idxidx-idx){bit[idx](bit[idx]delta)%MOD;}}intquery(intidx){intsum0;for(;idx0;idx-idx-idx){sum(sumbit[idx])%MOD;}returnsum;}};intmain(){ios::sync_with_stdio(false);cin.tie(0);cinT;for(intt1;tT;t){cinNM;vectorintvals;for(inti1;iN;i){cina[i];vals.push_back(a[i]);}// 离散化sort(vals.begin(),vals.end());vals.erase(unique(vals.begin(),vals.end()),vals.end());intszvals.size();for(inti1;iN;i){a[i]lower_bound(vals.begin(),vals.end(),a[i])-vals.begin()1;}// 初始化 dpmemset(dp,0,sizeof(dp));for(inti1;iN;i){dp[i][1]1;}// DPfor(intl2;lM;l){Fenwickft(sz);for(inti1;iN;i){dp[i][l]ft.query(a[i]-1);// 所有小于 a[i] 的 dp[j][l-1] 之和ft.update(a[i],dp[i][l-1]);// 加入 dp[i][l-1] 到树状数组}}// 计算结果intans0;for(inti1;iN;i){ans(ansdp[i][M])%MOD;}coutCase #t: ans\n;}return0;}样例验证输入2 3 2 1 2 3 3 2 3 2 1输出Case #1: 3 Case #2: 0与题目样例一致。这样我们就用DP\texttt{DP}DP 树状数组优化解决了这个问题。