讲解 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)\)。

完整代码：

<code>#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;

}