P9108 [PA2020] Malowanie płotu
题意：
给定 \(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)\)。
完整代码：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#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<=r;i++)
#define _For(i,l,r) for(register int i=r;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<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int n,m,st,s1,s2,s3,s4,mod;
int f[2][N],g[2][N];
bool End;
int main(){
n=read(),m=read(),mod=read();
For(i,1,m)
f[0][i]=(f[0][i-1]+i)%mod;
_For(i,1,m)
g[0][i]=(g[0][i+1]+m-i+1)%mod;
For(i,2,n){
st^=1;
For(j,0,m+1)
f[st][j]=g[st][j]=0;
s1=s2=s3=s4=0;
For(j,1,m){
s1=(s1+j)%mod;
s2=(s2+1ll*g[st^1][j+1]*j%mod)%mod;
s3=(s3+f[st^1][j-1])%mod;
s4=(s4+1ll*f[st^1][j-1]*(j-1)%mod)%mod;
f[st][j]=(1ll*s1*f[st^1][m]%mod-s2-1ll*s3*j%mod+s4+mod*2ll)%mod;
}
s1=s2=s3=s4=0;
_For(j,1,m){
s1=(s1+m-j+1)%mod;
s2=(s2+1ll*f[st^1][j-1]*(m-j+1)%mod)%mod;
s3=(s3+1ll*g[st^1][j+1]*j%mod)%mod;
s4=(s4+g[st^1][j+1])%mod;
g[st][j]=(1ll*s1*f[st^1][m]%mod-s2-s3+1ll*s4*(j-1)%mod+mod*2)%mod;
}
}
write(f[st][m]);
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}