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;
}

原文链接：P9108 [PA2020] Malowanie płotu