题解：P12742 [POI 2016 R3] 信使 Messenger

· · 题解

建议先看 P8502。

我们考虑设 f_{x, y, t} 表示从 x 恰经过 t 步到 y，且不在途中经过 x 的方案数，就有简单的转移

f_{x, y, t} = \sum_{(z, y) \in E} f_{x, z, t - 1}

每次转移完成后将 f_{x, x, t} \gets 0 即可保证途中不经过 x。

答案还要求途中不经过 y，考虑枚举不合法路径中 y 最后一次出现的位置 i，那么 i 之前只要途中不经过 x 即可，为 f_{x, y, i}；i 后还要求途中不经过 y，于是我们设 g_{x, y, t} 表示从 x 恰经过 t 步回到 x，且途中不经过 y 的方案数，就有答案

h_{x, y, t} = f_{x, y, t} - \sum_{i = 1}^{t - 1} f_{x, y, i}g_{y, x, t - i}

求 g_{x, y, t} 时考虑枚举不合法路径中 y 最后一次出现的位置 i，i 之前还是 f_{x, y, i}，而 i 后要求从 y 到 x 且途中不能经过 x 和 y，我们惊奇地发现这恰好是 h_{y, x, t - i}，于是

g_{x, y, t} = f_{x, x, t} - \sum_{i = 1}^{t - 1} f_{x, y, i}h_{y, x, t - i}

按上述式子转移即可，时间复杂度 \mathcal{O}(n^3d + n^2d^2 + q)。注意算完 g_{x, y, t} 之后再清空 f_{x, x, t} \gets 0。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 100 + 10, maxd = 50;

int n, m, mod, q;
int f[maxn][maxn][maxd + 10], g[maxn][maxn][maxd + 10], h[maxn][maxn][maxd + 10];
vector<int> a[maxn];

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x x, Tp_y y){
    return x += y, x >= mod ? x -= mod : x;
}

template<typename Tp_x, typename Tp_y>
inline int self_mod_add(Tp_x &x, Tp_y y){
    return x = mod_add(x, y);
}

template<typename Tp, typename... Arg>
inline int mod_add(Tp x, Arg ...args){
    return x += mod_add(args...), x >= mod ? x -= mod : x;
}

int main(){
    scanf("%d %d %d", &n, &m, &mod);
    for (int i = 1; i <= m; i++){
        int u, v;
        scanf("%d %d", &u, &v), a[u].push_back(v);
    }
    for (int i = 1; i <= n; i++){
        f[i][i][0] = h[i][i][0] = 1;
        for (int j = 1; j <= n; j++){
            g[i][j][0] = 1;
        }
    }
    for (int i = 1; i <= maxd; i++){
        for (int u = 1; u <= n; u++){
            for (auto v: a[u]){
                for (int j = 1; j <= n; j++){
                    self_mod_add(f[j][v][i], f[j][u][i - 1]);
                }
            }
        }
        for (int j = 1; j <= n; j++){
            for (int k = 1; k <= n; k++){
                h[j][k][i] = f[j][k][i], g[j][k][i] = f[j][j][i];
                for (int x = 1; x < i; x++){
                    self_mod_add(h[j][k][i], mod - (long long)f[j][k][x] * g[k][j][i - x] % mod);
                    self_mod_add(g[j][k][i], mod - (long long)f[j][k][x] * h[k][j][i - x] % mod);
                }
            }
        }
        for (int j = 1; j <= n; j++){
            f[j][j][i] = 0;
        }
    }
    scanf("%d", &q);
    while (q--){
        int x, y, d;
        scanf("%d %d %d", &x, &y, &d), printf("%d\n", h[x][y][d]);
    }

return 0;
}