题意：
给定 \(n,m\)，一个区间序列 \(\{[L_1,R_1],[L_2,R_2],\cdots,[L_n,R_n]\}\) 被称为好的当且仅当：
- \(\forall i \in [1,n],1 \le L_i \le R_i \le m\)。
- \(\forall i \in [1,n-1],[L_i,R_i] \cup [L_{i+1},R_{i+1}] \ne \emptyset\)。
输出好的序列个数对给定质数 \(p\) 取模的结果
\(nm \le 10^7\)。
思路：
考虑动态规划算法，定义 \(dp_{i,l,r}\) 表示第 \(i\) 次为 \([l,r]\)，则状态转移方程为：
\[dp_{i,l,r} = \sum_{L=1}^r \sum_{R=\max(L,l)}^m dp_{L,R}\]
这种是不好转移的，考虑做一个容斥，用总的减去与 \(L \le R < l\) 或 \(r< L \le R\) 的贡献，记 \(s_i\) 表示所有 \(dp_{i,l,r}\) 的和：
\[dp_{i,l,r} = s_{i-1} - \sum_{L=1}^{l-1} \sum_{R=L}^{l-1} dp_{L,R} - \sum_{L=r+1}^m \sum_{R=L}^m dp_{L,R}\]
我们可以记 \(f_{i,j}\) 表示所有满意 \(r \le j\) 的 \(dp_{i,l,r}\) 的和，记 \(g_{i,j}\) 满意所有 \(j \le l\) 的 \(dp_{i,l,r}\) 的和，则状态转移方程更新为：
\[dp_{i,l,r} = f_{i-1,m} - f_{i-1,l-1} - g_{i-1,r+1}\]
时间复杂度通过前缀和优化至 \(O(nm^2)\)，考虑继续优化。
考虑如何快速求 \(f_{i,j}\) 和 \(g_{i,j}\)，可以直接爆推：
\[\begin{aligned} f_{i,j} &= \sum_{l=1}^j \sum_{r=l}^j dp_{i,l,r} \\ &= \sum_{l=1}^j \sum_{r=l}^j f_{i-1,m} - f_{i-1,l-1} - g_{i-1,r+1} \\ & = \frac{j(j+1)}{2} f_{i-1,m} - \Big( \sum_{l=1}^j \sum_{r=l}^j f_{i-1,l-1} + g_{i-1,r+1} \Big) \\ &= \frac{j(j+1)}{2} f_{i-1,m} - \sum_{l=1}^j (j-l+1) \times f_{i-1,l-1} - \sum_{r=1}^j r \times g_{i-1,r+1} \\ &= \frac{j(j+1)}{2} f_{i-1,m} - \sum_{r=1}^j r \times g_{i-1,r+1} - \Big( \sum_{l=1}^j j \times f_{i-1,l-1} - \sum_{l=1}^j (l-1) \times f_{i-1,l-1} \Big) \\ &= \frac{j(j+1)}{2} f_{i-1,m} - \sum_{r=1}^j r \times g_{i-1,r+1} - j\sum_{l=1}^j f_{i-1,l-1} + \sum_{l=1}^j (l-1) \times f_{i-1,l-1} \end{aligned}\]
\[\begin{aligned} g_{i,j} &= \sum_{l=j}^m \sum_{r=l}^m dp_{i,l,r} \\ &= \sum_{l=j}^m \sum_{r=l}^m f_{i-1,m} - f_{i-1,l-1} - g_{i-1,r+1} \\ &= \frac{(m+j)(m-j+1)}{2} f_{i-1,m} - \Big(\sum_{l=j}^m \sum_{r=l}^m f_{i-1,l-1} + g_{i-1,r+1} \Big) \\ &= \frac{(m+j)(m-j+1)}{2} f_{i-1,m} - \sum_{l=j}^m (m-l+1) f_{i-1,l-1}-\sum_{r=j}^m (r-j + 1) g_{i-1,r+1} \\ & = \frac{(m+j)(m-j+1)}{2} f_{i-1,m} - \sum_{l=j}^m (m-l+1) f_{i-1,l-1} - \sum_{r=j}^m r \times g_{i-1,r+1} + (j-1) \sum_{r=j}^m g_{i-1,r+1} \end{aligned}\]
如许时间复杂度优化为 \(O(nm)\)。
完整代码：
[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod) x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(register int i=l;i=l;i--)using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const int N=1e7+10; inline int read(){ int x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c |
