Luogu P10027 梦境世界 题解 [ 蓝 ] [ 多维 DP ]

梦境世界：可爱 DP 题。

一种常见的假做法是在 DP 的过程中记录路径的前驱进行转移，这种做法错误的原因并不在于转移存在环，它其实就是一张 DAG，但是这种状态表示方式并不能推导出前驱的前驱是谁，所以才是假的。

考虑正解。观察路径，发现路径一定由正常走、回溯走、正常走、回溯走的周期进行。因此我们可以在方格取数式的 DP 中给每个转移加一个系数，表示在进行这次移动之前，先进行了 \(x\) 次移动并且用 \(x\) 次回溯回到了原位。强制钦定回到原位的原因是因为这样才可以清晰地划分路径的状态。

剩下的就是简单的了，我们分两个 DP 做：

• 先求出 \(g_{i, j, k}\)，表示走到 \((i, j)\)，在接下来的路线中先走 \(k\) 步，然后再回溯 \(k\) 步，回到 \((i, j)\) 的方案数。类似背包，利用乘法原理转移即可。注意需要倒着枚举 \(i, j\)。
• 再求出 \(f_{i, j, k}\)，表示走到 \((i, j)\)，已经用了 \(k\) 次回溯的方案数。转移和方格取数差不多，但是需要加上 \(g\) 的系数。

时间复杂度 \(O(n^4)\)，如果被卡常可以考虑调换 DP 三个维度的顺序和取模卡常。

#include<bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 105;
int n, m, p, s, f[N][N][N], g[N][N][N], mod;
bitset<N> ban[N];
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> p >> mod >> s;while(s--){int x, y;cin >> x >> y;ban[x][y] = 1;}for(int lv = 0; lv <= p; lv++){for(int i = n; i >= 1; i--){for(int j = m; j >= 1; j--){if(lv == 0){if(ban[i][j] == 0) g[i][j][0] = 1;continue;}if(i + 1 <= n && ban[i + 1][j] == 0){for(int c = 0; c < lv; c++){g[i][j][lv] += (1ll * g[i][j][lv - c - 1] * g[i + 1][j][c]) % mod;if(g[i][j][lv] >= mod) g[i][j][lv] -= mod;}}                    if(j + 1 <= m && ban[i][j + 1] == 0){for(int c = 0; c < lv; c++){g[i][j][lv] += (1ll * g[i][j][lv - c - 1] * g[i][j + 1][c]) % mod;if(g[i][j][lv] >= mod) g[i][j][lv] -= mod;}}}}}f[1][1][0] = 1;for(int lv = 0; lv <= p; lv++){for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(ban[i][j]) continue;if(i + 1 <= n && ban[i + 1][j] == 0){for(int c = 0; c + lv <= p; c++){f[i + 1][j][c + lv] += (1ll * f[i][j][lv] * g[i][j][c]) % mod;if(f[i + 1][j][c + lv] >= mod) f[i + 1][j][c + lv] -= mod;}}if(j + 1 <= m && ban[i][j + 1] == 0){for(int c = 0; c + lv <= p; c++){f[i][j + 1][c + lv] += (1ll * f[i][j][lv] * g[i][j][c]) % mod;if(f[i][j + 1][c + lv] >= mod) f[i][j + 1][c + lv] -= mod;}}}}}int ans = 0;for(int i = 0; i <= p; i++) ans = (ans + f[n][m][i]) % mod;cout << ans;return 0;
}