%赛场切了！
矩阵是不太好处理的，所以考虑从一行去推下一行。
设上一行选择了 \(p_1,p_2,\cdots,p_k\) 这几个横坐标的位置为 \(1\)，分情况讨论一下这一行选择的 \(x\) 位置。
（下列结合自己画图理解）
- \(x\ge p_1\)。
首先发现如果选择一个 \(x\not\in p\)，则一定不满足条件。
然后也可以发现，设这一行的选择的 \(x\ge p_1\) 的部分为 \(q\)，则 \(q\) 是 \(p\) 的一个前缀。
但是又发现，如果有一行完全不选，则这一行状态可以视为继承上一行的。这个要特判一下。
- \(x<p_1\)。
结合前面，发现可以任选。
于是我们可以开始 dp 了。
设 \(dp_{i,j,k}\) 表示枚举到第 \(i\) 行，这一行选了 \(j\) 个 \(1\)，最左侧的 \(1\) 左边还有 \(k\) 个 \(0\) 的方案数。
首先转移 \(x\ge p_1\) 的情况。枚举转移到长度为 \(l\) 的前缀，直接转移即可。
然后在上一步的基础上转移 \(x<p_1\) 的。枚举选 \(a\) 个，最左边一个左边有 \(l\) 个 \(0\)，另用一个数组转移。最后全部加到一起。
于是能写出如下 \(O(n^5)\) 的代码，\(n,m\) 同阶：
点击查看代码
fac[0]=1;
rep(i,1,m)fac[i]=1ll*fac[i-1]*i%mod;
ifac[m]=qpow(fac[m],mod-2);
drep(i,m-1,0)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
rep(i,1,m)rep(j,0,m)dp[1][i][j]=binom(m-j-1,i-1);
dp[1][0][m]=1;
rep(i,2,n){
mems(f,0);
rep(j,0,m){
rep(k,0,m){
rep(l,0,j)dp[i][l][k]=Mod(dp[i][l][k],dp[i-1][j][k]);
if(j)f[j][k]=Mod(f[j][k],dp[i-1][j][k]),f[0][k]=Mod(f[0][k],mod-dp[i-1][j][k]);
}
}
rep(j,0,m){
rep(k,0,m){
rep(l,1,k)rep(p,0,k-l)f[j+p+1][l-1]=Mod(f[j+p+1][l-1],1ll*dp[i][j][k]*binom(k-l,p)%mod);
}
}
rep(j,0,m)rep(k,0,m)dp[i][j][k]=Mod(dp[i][j][k],f[j][k]);
}
int ans=0;
rep(i,0,m)rep(j,0,m)ans=Mod(ans,dp[n][i][j]);
printf("%d\n",ans);
然后开始优化！
发现我们的状态已经足够优秀了。从转移入手。
瓶颈在 \(x<p_1\) 的部分。然后发现这一部分其实没必要枚举两个值，可以再用一次 dp 去转移，每次枚举左边下一个点选什么，以此转移。变成 \(O(n^4)\)。
点击查看代码
rep(i,2,n){
mems(f,0),mems(g,0);
rep(j,0,m){
rep(k,0,m){
rep(l,0,j)f[l][k]=Mod(f[l][k],dp[i-1][j][k]);
if(j)dp[i][j][k]=Mod(dp[i][j][k],dp[i-1][j][k]),dp[i][0][k]=Mod(dp[i][0][k],mod-dp[i-1][j][k]);
}
}
rep(j,0,m){
drep(k,m,0){
rep(l,1,k)f[j+1][l-1]=Mod(f[j+1][l-1],f[j][k]);
}
}
rep(j,0,m)rep(k,0,m)dp[i][j][k]=Mod(dp[i][j][k],f[j][k]);
}
然后继续优化！
发现上面的 \(f_{l,k}\) 的转移是从 \(dp_{i,[l,m],k}\) 来的，于是可以变一下枚举顺序然后前缀和，复杂度少一个 \(n\)。然后下面也可以一样处理。
于是变成了 \(O(n^3)\)：
点击查看代码
rep(i,2,n){
mems(f,0);
rep(k,0,m){
s[0]=dp[i-1][0][k];
rep(j,1,m)s[j]=Mod(s[j-1],dp[i-1][j][k]);
rep(l,0,m)f[l][k]=Mod(f[l][k],Mod(s[m],mod-s[l-1]));
}
rep(j,0,m){
rep(k,0,m){
if(j)dp[i][j][k]=Mod(dp[i][j][k],dp[i-1][j][k]),dp[i][0][k]=Mod(dp[i][0][k],mod-dp[i-1][j][k]);
}
}
rep(j,0,m){
s[0]=0;
rep(k,1,m)s[k]=Mod(s[k-1],f[j][k]);
drep(l,m,1){
f[j+1][l-1]=Mod(f[j+1][l-1],Mod(s[m],mod-s[l-1]));
}
}
rep(j,0,m)rep(k,0,m)dp[i][j][k]=Mod(dp[i][j][k],f[j][k]);
}
然后可能被卡空间，使滚动，空间 \(O(n^2)\)。可以通过。
code：
int n,m,dp[2][N][N],f[N][N],s[N];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
void solve3(){
dp[0][0][m]=1;
rep(i,1,n){
int p=i&1;
mems(f,0),mems(dp[p],0);
rep(k,0,m){
s[0]=dp[p^1][0][k];
rep(j,1,m)s[j]=Mod(s[j-1],dp[p^1][j][k]);
rep(l,0,m)f[l][k]=Mod(f[l][k],Mod(s[m],mod-s[l-1]));
}
rep(j,0,m){
rep(k,0,m){
if(j)dp[p][j][k]=Mod(dp[p][j][k],dp[p^1][j][k]),dp[p][0][k]=Mod(dp[p][0][k],mod-dp[p^1][j][k]);
}
}
rep(j,0,m){
s[0]=0;
rep(k,1,m)s[k]=Mod(s[k-1],f[j][k]);
drep(l,m,1)f[j+1][l-1]=Mod(f[j+1][l-1],Mod(s[m],mod-s[l-1]));
}
rep(j,0,m)rep(k,0,m)dp[p][j][k]=Mod(dp[p][j][k],f[j][k]);
}
int ans=0;
rep(i,0,m)rep(j,0,m)ans=Mod(ans,dp[n&1][i][j]);
printf("%d\n",ans);
}
void Yorushika(){
scanf("%d%d",&n,&m);
solve3();
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
横向对比，发现这个方法不需要组合数，所以事实上是可以做任意模数的！
标签：ARC162F,int,rep,ans,Mod,dp,mod From： https://www.cnblogs.com/yinhee/p/17968097/ARC162F