题目。
考虑 DP。由于撤销操作会导致环路，所以不能直接 DP。
我们发现对于撤销操作肯定会回到某一个点，也就是存在一个点，走了若干步再撤回再走。这样就好转移了。
定义 (G_{i,j,k}) 代表从 ((i,j)) 出发，拥有 (k) 瓶撤销药，到达终点的方案数。
同时，我们定义 (F_{i,j,k}) 为从 ((i,j)) 出发，消耗 (k) 个药，最后返回 ((i,j)) 的种类数。
注意，这里的 (k) 代表循环变量，题目中的 (k) 以 (K) 表示。
可以发现转移公式就是 (forall xin[0,k])，也就是当前节点走出去再回来消耗的药的个数，将 (F_{i,j,x} imes(G_{i+1,j,k-x}+G_{i,j+1,k-x})) 求和就是 (G_{i,j,k})。即：
[G_{i,j,k}=sum_{x=0}^kF_{i,j,x} imes(G_{i+1,j,k-x}+G_{i,j+1,k-x})
]
答案就是：
[sum_{k=1}^KG_{1,1,k}
]
现在考虑计算 (F_{i,j,k})。很显然，(F_{i,j,k}) 就是往下或往右走 (1) 格再走 (k-x-1) 步之后退回来，然后再在原地走 (x) 步。转移式：
[F_{i,j,k}=sum_{x=0}^{k-1}F_{i,j,x} imes(F_{i+1,j,k-x-1}+F_{i,j+1,k-x-1})
]
转移的注意事项：
- 转移 (G_{i,j,k}) 时 (i,j) 要逆序。
- 最外层是 (k)。
时间复杂度：(Theta(nmk^2))，空间复杂度：(Theta(nmk))。
#include <bits/stdc++.h>
#define For(i, l, r) for(int i = l, i##QWQ = r; i <= i##QWQ; i++)
#define Rev(i, l, r) for(int i = l, i##QWQ = r; i >= i##QWQ; i--)
using namespace std;
const int N = 105;
int F[N][N][N], G[N][N][N], mp[N][N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, K, p, s, ans = 0; cin >> n >> m >> K >> p >> s;
for(int x, y; s-- && cin >> x >> y;) mp[x][y] = 1;
For(i, 1, n) For(j, 1, m) if(!mp[i][j]) F[i][j][0] = 1;
For(k, 1, K) For(i, 1, n) For(j, 1, m) if(!mp[i][j]) For(x, 0, k - 1)
F[i][j][k] = (F[i][j][k] + 1ll * F[i][j][x] * (F[i + 1][j][k - x - 1] + F[i][j + 1][k - x - 1]) % p) % p;
G[n][m][0] = 1;
For(k, 0, K) Rev(i, n, 1) Rev(j, m, 1) if(!mp[i][j]) For(x, 0, k)//i,j逆序
G[i][j][k] = (G[i][j][k] + 1ll * F[i][j][x] * (G[i + 1][j][k - x] + G[i][j + 1][k - x]) % p) % p;
For(k, 0, K) ans = (ans + G[1][1][k]) % p;
cout << ans << "
";
return 0;
}