题解：P10027 梦境世界

一个 dp。

首先我们将整条路径分别看作「有效路径」和「无效路径」。容易知道：

- 有效路径是不会被撤回的，且长度为 $n+m-1$。
- 无效路径都会被撤回。假设你位于点 $(i,j)$，那么你在这个点出发任意地走无效路径，最终都会回到点 $(i,j)$。

我们设 $F(i,j,k)$ 表示从点 $(i,j)$ 出发，走到终点 $(n,m)$，且使用 $k$ 次撤回的方案数。

容易得出转移 $F(i,j,k)=\displaystyle \sum\limits_{t=0}^k[F(i+1,j,k-t)+F(i,j+1,k-t)]\times G(i,j,t)$。

其中，$G(i,j,k)$ 表示在点 $(i,j)$ 花费 $k$ 次撤回，走无效路径的方案数。

有 $G(i,j,k)=\displaystyle \sum \limits_{t=1}^k[G(i+1,j,t-1)+G(i,j+1,t-1)]\times G(i,j,k-t)$。

时间复杂度 $O(n^4)$。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--) 
const int N=109;
int n,m,K,p,ans,s;
int a[N][N],F[N][N][N],G[N][N][N];
signed main()
{
	cin>>n>>m>>K>>p>>s;
	const int mod=p;
	rep(i,1,n) rep(j,1,m) a[i][j]=1;
	while(s--){
		int x,y;
		cin>>x>>y;
		a[x][y]=0;
	}
	rep(i,1,n) rep(j,1,m) G[i][j][0]=a[i][j];
	per(i,n,1){
		per(j,m,1){
			if(a[i][j]==0){
				F[i][j][0]=0;
				continue;
			}
			if(i==n&&j==m) F[i][j][0]=1;
			else{
				F[i][j][0]=(F[i+1][j][0]+F[i][j+1][0])%mod;
			}
		}
	}
	rep(k,1,K){
		per(i,n,1){
			per(j,m,1){
				int sum=0;
				rep(t,1,k){
					sum=(sum+(G[i+1][j][t-1]+G[i][j+1][t-1])*G[i][j][k-t])%mod;
				}
				G[i][j][k]=sum;
			}
		}
	}
	rep(k,1,K){
		per(i,n,1){
			per(j,m,1){
				int sum=0;
				rep(t,0,k){
					sum=(sum+(F[i+1][j][k-t]+F[i][j+1][k-t])*G[i][j][t])%mod;
				}
				F[i][j][k]=sum;
			}
		}
	}
	rep(k,0,K) ans=(ans+F[1][1][k])%mod;
	cout<<ans<<"\n";
	return 0;
}
```

正在渲染内容...