题目链接

题目描述

$n$ 个点的DAG,三个人要求位于三个两两点权差值不超过 $K$ 的点

每次三个人可以停止任务或者沿着边同时移动一步,求合法路线的方案数

$n \le 60$

$q \le 2.5 \times 10^5$

简要做法

设 $f(i,j,k)$ 表示三个人分别在 $(i,j,k)$ 时接着往下走的方案数

枚举每个人的下一步位置进行转移

状态数 $O(n^3)$,每个状态的转移时间复杂度为 $O(n^3)$

总时间复杂度 $O(n^6 + q)$

拆解一步转移的过程:三个人同时选择下一步位置 -> 第一个人先选,第二个人再选,第三个人最后选

考虑加维,设 $f(i,j,k,now)$ 表示三个人分别在 $(i,j,k)$ 时,目前准备走 $now$ 这个人的方案数

枚举 $now$ 这个人的下一步位置进行转移。

三个人都走了一步后,再将不符合点权差值限制的状态排除

状态数 $O(n^3)$,每个状态的转移时间复杂度为 $O(n)$

总时间复杂度 $O(n^4 + q)$

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <math.h>

#define int long long

const int N = 60 + 5;
const int P = 998244353;

int n, m, K, q;
int w[N], f[N][N][N][3];
bool G[N][N];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

signed main()
{
    // freopen("agent.in", "r", stdin), freopen("agent.out", "w", stdout);
    for (int T = read(); T--;)
    {
        memset(G, 0, sizeof G), memset(f, 0, sizeof f);
        n = read(), m = read(), K = read(), q = read();
        for (int i = 1; i <= n; i++)
            w[i] = read();
        for (int i = 1, u, v; i <= m; i++)
            u = read(), v = read(), G[u][v] = true;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= n; k++)
                    f[i][j][k][0] = (abs(w[i] - w[j]) <= K and abs(w[i] - w[k]) <= K and abs(w[j] - w[k]) <= K);
        for (int i = n; i >= 1; i--)
            for (int j = n; j >= 1; j--)
                for (int k = n; k >= 1; k--)
                    for (int l = 1; l <= n; l++)
                    {
                        if (G[i][l] and f[i][j][k][0])
                            (f[i][j][k][0] += f[l][j][k][1] % P) %= P;
                        if (G[j][l])
                            (f[i][j][k][1] += f[i][l][k][2] % P) %= P;
                        if (G[k][l])
                            (f[i][j][k][2] += f[i][j][l][0] % P) %= P;
                    }
        for (int x, y, z; q--;)
            x = read(), y = read(), z = read(), printf("%lld\n", f[x][y][z][0] % P);
    }
    return 0;
}