绝世前缀和优化 DP 好题。
题意分析
即找出长度为 $n$ 的序列 $\langle[l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\rangle$ 的个数，且满足：
- $l_i,r_i$ 为整数，且 $1\leq l_i\leq r_i\leq m$。
- 对于 $1\leq i<n$，有 $[l_i,r_i],[l_{i+1},r_{i+1}]$ 相交。
朴素 DP
设 $\textit{dp}_{i,l,r}$ 为第 $i$ 项为 $[l,r]$ 的方案数。
枚举第 $i-1$ 项 $[l_2,r_2]$，有：
\[\textit{dp}_{i,l,r}=\sum_{l_2=1}^m\sum_{r_2=l_2}^{m}[[l,r]\cap[l_2,r_2]\neq\varnothing]\textit{dp}_{i-1,l_2,r_2}\]答案即：
\[\sum_{l=1}^m\sum_{r=l}^m\textit{dp}_{n,l,r}\]朴素转移 $\mathcal O\left(nm^4\right)$。
前缀和优化 DP
发现，与区间 $[l,r]$ 有交的 $[l_2,r_2]$ 可以用所有合法区间减去无交区间得到。
因此可以有：
\[\begin{aligned} \textit{dp}_{i,l,r}&=\sum_{l_2=1}^m\sum_{r_2=l_2}^{m}[[l,r]\cap[l_2,r_2]\neq\varnothing]\textit{dp}_{i-1,l_2,r_2}\\ &=\sum_{l_2=1}^m\sum_{r_2=l_2}^m\textit{dp}_{i-1,l_2,r_2}-\sum_{l_2=r+1}^m\sum_{r_2=l_2}^m\textit{dp}_{i-1,l_2,r_2}-\sum_{r_2=l-1}^m\sum_{l=1}^{r_2}\textit{dp}_{i-1,l_2,r_2} \end{aligned}\]显然可以维护 $\textit{dp}_{i-1,l,r}$ 的所有状态的和 $\textit{sum}_i$，即：
\[\textit{sum}_i=\sum_{l=1}^m\sum_{r=l}^m\textit{dp}_{i,l,r}\]故有：
\[\textit{dp}_{i,l,r}=\textit{sum}_{i-1}-\sum_{l_2=r+1}^m\sum_{r_2=l_2}^m\textit{dp}_{i-1,l_2,r_2}-\sum_{r_2=l-1}^m\sum_{l=1}^{r_2}\textit{dp}_{i-1,l_2,r_2}\]考虑优化后面的部分。
对于 $\displaystyle\sum_{l=x+1}^m\sum_{r=l}^m\textit{dp}_{i-1,l,r}$，即 $x$ 右边的所有 DP 值之和。显然可以使用后缀和优化。
记：
\[\begin{aligned} \displaystyle\textit{suf}_{i,x}&=\textit{suf}_{i+1,x}+\sum_{r=x}^m\textit{dp}_{i,x,r}\\ \displaystyle\textit{pre}_{i,x}&=\textit{pre}_{i-1,x}+\sum_{l=1}^x\textit{dp}_{i,l,x} \end{aligned}\]分别表示 $x$ 及其右边的所有区间的方案数和 $x$ 及其左边的所有区间的方案数。
这显然可以在求解 DP 时求出来。
因此可以有：
\[\textit{dp}_{i,l,r}=\textit{sum}_{i-1}-\textit{suf}_{i-1,r+1}-\textit{pre}_{i-1,l-1}\]发现，此时答案即 $\textit{suf}{n,1}$。又可以发现，此时状态 $\textit{dp}{i,l,r}$ 已经没有意义。
$\textit{sum}_i$ 可以进一步优化：
\[\begin{aligned} \textit{sum}_i&=\sum_{l=1}^m\sum_{r=l}^m\textit{dp}_{i,l,r}\\ &=\sum_{l=1}^m\sum_{r=l}^m\left(\textit{sum}_{i-1}-\textit{suf}_{i-1,r+1}-\textit{pre}_{i-1,l-1}\right)\\ &=\sum_{l=1}^m\left((m-l+1)(\textit{sum}_{i-1}-\textit{pre}_{i-1,l-1})-\sum_{r=l}^{m}\textit{suf}_{i-1,r+1}\right) \end{aligned}\]这启发我们可以维护 $\displaystyle\sum_{r=l}^{m}\textit{suf}_{i-1,r+1}$ 的后缀和来优化。因此记：
\[\begin{aligned} \textit{sufSumSuf}_{i,x}&=\sum_{l=x}^m\textit{suf}_{i,x}\\ &=\textit{sufSumSuf}_{i,x+1}+\textit{suf}_{i,x}\\ \textit{preSumPre}_{i,x}&=\sum_{r=x}^m\textit{pre}_{i,x}\\ &=\textit{preSumPre}_{i,x+1}+\textit{pre}_{i,x}\\ \end{aligned}\]则可以将 $\textit{sum}_i$ 的递推转化为：
\[\textit{sum}_i=\sum_{l=1}^m\left((m-l+1)(\textit{sum}_{i-1}-\textit{pre}_{i-1,l-1})-\textit{sufSumSuf}_{l+1}\right)\]同样地，代入可以更改 $\textit{pre}{i,x},\textit{suf}{i,x}$ 的递推式，最终与 $\textit{dp}_{i,l,r}$ 无关。有：
\[\begin{aligned} \textit{pre}_{i,x}&=\textit{pre}_{i,x-1}+x\left(\textit{sum}_{i-1}-\textit{suf}_{i-1,x+1}\right)-\textit{preSumPre}_{i-1,x-1}\\ \textit{suf}_{i,x}&=\textit{suf}_{i,x+1}+(m-x+1)\left(\textit{sum}_{i-1}-\textit{pre}_{i-1,x-1}\right)-\textit{preSumPre}_{i-1,x+1}\\ \end{aligned}\]此时状态量为 $\mathcal O(nm)$，转移 $\mathcal O(1)$。
时间复杂度：$\mathcal O(nm)$。由于 $1\leq nm\leq10^7$，可以通过。
使用滚动数组，而不要使用 vector 套 vector。会被卡空间。
AC 代码
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
69
70
71
72
73
74
75
76
77
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e7,M=1e7;
int n,m,P,ans;
int sum[2],pre[2][N+1],preSumPre[2][N+1],suf[2][N+1],sufSumSuf[2][N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>P;
bool op=0;
for(int l=1;l<=m;l++){
suf[op][l]=m-l+1;
}
for(int r=1;r<=m;r++){
pre[op][r]=r;
}
sum[op]=(m*(m+1ll)>>1)%P;
for(int r=1;r<=m;r++){
pre[op][r]=(pre[op][r]+pre[op][r-1])%P;
preSumPre[op][r]=(pre[op][r]+preSumPre[op][r-1])%P;
}
sufSumSuf[op][m]=suf[op][m];
for(int l=m-1;1<=l;l--){
suf[op][l]=(suf[op][l+1]+suf[op][l])%P;
sufSumSuf[op][l]=(suf[op][l]+sufSumSuf[op][l+1])%P;
}
for(int i=2;i<=n;i++){
op=!op;
sum[op]=0;
for(int r=1;r<=m;r++){
pre[op][r]=(1ll*r*(sum[!op]-suf[!op][r+1])-preSumPre[!op][r-1])%P;
}
for(int l=1;l<=m;l++){
suf[op][l]=((m-l+1ll)*(sum[!op]-pre[!op][l-1])-sufSumSuf[!op][l+1])%P;
}
for(int l=1;l<=m;l++){
sum[op]=(sum[op]+(m-l+1ll)*(sum[!op]-pre[!op][l-1])%P-sufSumSuf[!op][l+1])%P;
}
for(int r=1;r<=m;r++){
pre[op][r]=(pre[op][r]+pre[op][r-1])%P;
preSumPre[op][r]=(pre[op][r]+preSumPre[op][r-1])%P;
}
sufSumSuf[op][m]=suf[op][m];
for(int l=m-1;1<=l;l--){
suf[op][l]=(suf[op][l+1]+suf[op][l])%P;
sufSumSuf[op][l]=(suf[op][l]+sufSumSuf[op][l+1])%P;
}
}
int ans=suf[op][1];
if(ans<0){
ans+=P;
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
