题意:
给定 \(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]\),则状态转移方程为:
这种是不好转移的,考虑做一个容斥,用总的减去与 \(L \le R < l\) 或 \(r< L \le R\) 的贡献,记 \(s_i\) 表示所有 \(dp_{i,l,r}\) 的和:
我们可以记 \(f_{i,j}\) 表示所有满足 \(r \le j\) 的 \(dp_{i,l,r}\) 的和,记 \(g_{i,j}\) 满足所有 \(j \le l\) 的 \(dp_{i,l,r}\) 的和,则状态转移方程更新为:
时间复杂度通过前缀和优化至 \(O(nm^2)\),考虑继续优化。
考虑如何快速求 \(f_{i,j}\) 和 \(g_{i,j}\),可以直接爆推:
这样时间复杂度优化为 \(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;
}