专栏文章

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

CClaire0918
P12742题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjwv6n
此快照首次捕获于
2025/12/02 03:37
3 个月前
此快照最后确认于
2025/12/02 03:37
3 个月前
查看原文
建议先看 P8502。
我们考虑设 fx,y,tf_{x, y, t} 表示从 xx 恰经过 tt 步到 yy，且不在途中经过 xx 的方案数，就有简单的转移
fx,y,t=∑(z,y)∈Efx,z,t−1f_{x, y, t} = \sum_{(z, y) \in E} f_{x, z, t - 1}
每次转移完成后将 fx,x,t←0f_{x, x, t} \gets 0 即可保证途中不经过 xx。
答案还要求途中不经过 yy，考虑枚举不合法路径中 yy 最后一次出现的位置 ii，那么 ii 之前只要途中不经过 xx 即可，为 fx,y,if_{x, y, i}；ii 后还要求途中不经过 yy，于是我们设 gx,y,tg_{x, y, t} 表示从 xx 恰经过 tt 步回到 xx，且途中不经过 yy 的方案数，就有答案
hx,y,t=fx,y,t−∑i=1t−1fx,y,igy,x,t−ih_{x, y, t} = f_{x, y, t} - \sum_{i = 1}^{t - 1} f_{x, y, i}g_{y, x, t - i}
求 gx,y,tg_{x, y, t} 时考虑枚举不合法路径中 yy 最后一次出现的位置 ii，ii 之前还是 fx,y,if_{x, y, i}，而 ii 后要求从 yy 到 xx 且途中不能经过 xx 和 yy，我们惊奇地发现这恰好是 hy,x,t−ih_{y, x, t - i}，于是
gx,y,t=fx,x,t−∑i=1t−1fx,y,ihy,x,t−ig_{x, y, t} = f_{x, x, t} - \sum_{i = 1}^{t - 1} f_{x, y, i}h_{y, x, t - i}
按上述式子转移即可，时间复杂度 O(n3d+n2d2+q)\mathcal{O}(n^3d + n^2d^2 + q)。注意算完 gx,y,tg_{x, y, t} 之后再清空 fx,x,t←0f_{x, x, t} \gets 0。
Code：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...