传球游戏

GitHub 跳转原题关系图返回列表

把出现在限制边中的球员和 1 号球员单独作为特殊点，其余球员合并成一个普通组，做 m 轮压缩 DP。

OJ: luogu

题目 ID: P5888

难度:普及+/提高

标签:动态规划图论dp

日期: 2026-06-19 13:31

题意

有 $n$ 个球员，初始球在 $1$ 号手中。

一共传 $m$ 次，每次必须把球传给别人，不能传给自己。除此之外，还额外给出 $k$ 条禁止边 $a \to b$ ，表示 $a$ 号球员不能把球传给 $b$ 号球员。

要求统计第 $m$ 次传球后，球回到 $1$ 号球员手中的方案数。

思路

先看小数据下最直接的做法：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据直接在完整图上做 m 轮 DP，用来帮助理解和辅助对拍。

const int MOD = 998244353;

int n, m, k;
bool ban_edge[205][205];
int dp[205], ndp[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        if (a != b) {
            ban_edge[a][b] = true;
        }
    }

    dp[1] = 1;

    for (int step = 1; step <= m; step++) {
        for (int i = 1; i <= n; i++) {
            ndp[i] = 0;
        }

        for (int u = 1; u <= n; u++) {
            if (dp[u] == 0) {
                continue;
            }
            for (int v = 1; v <= n; v++) {
                if (u == v || ban_edge[u][v]) {
                    continue;
                }
                ndp[v] += dp[u];
                if (ndp[v] >= MOD) {
                    ndp[v] -= MOD;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            dp[i] = ndp[i];
        }
    }

    cout << dp[1] << '\n';
    return 0;
}

下面是另一种「状态搜索」风格的暴力写法。它把状态写成"已经传了几次、球在谁手中"，递归枚举下一轮传给哪个球员，重复状态用记忆化保存：

另一种暴力写法：状态搜索

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55// brute_01_style.cpp：状态搜索风格暴力，把“传了几次、球在谁手中”作为状态。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const int MAXM = 205;
const int MOD = 998244353;

int n, m, k;
bool ban_edge[MAXN][MAXN];
int memo[MAXM][MAXN];
bool vis[MAXM][MAXN];

// dfs_pass(step, u)：已经传了 step 次，球在 u 手中，继续枚举下一轮传给谁。
int dfs_pass(int step, int u) {
    if (step == m) {
        return u == 1;
    }

    if (vis[step][u]) {
        return memo[step][u];
    }
    vis[step][u] = true;

    int ways = 0;
    for (int v = 1; v <= n; v++) {
        if (v == u || ban_edge[u][v]) {
            continue;
        }
        ways += dfs_pass(step + 1, v);
        if (ways >= MOD) {
            ways -= MOD;
        }
    }

    memo[step][u] = ways;
    return ways;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        if (a != b) {
            ban_edge[a][b] = true;
        }
    }

    cout << dfs_pass(0, 1) << '\n';
    return 0;
}

brute.cpp 就是在完整图上做普通 DP：
$dp[t][u]$ 表示传了 $t$ 次后，球在 $u$ 号球员手中的方案数，然后枚举所有合法下一手。

这个思路没问题，但 $n$ 可以到 $10^9$ ，根本不可能把每个球员都开状态。

关键观察是：虽然球员总数很多，但真正"特殊"的球员只有两类：

出现在某条非自环限制边里的球员
$1$ 号球员

把这些点单独拿出来，剩下的点都叫"普通点"。

因为普通点：

没有额外禁止入边
也没有额外禁止出边

所以任意一步后，所有普通点的方案数一定都相同，可以合并成一个状态。

状态表

这张表展示压缩后的状态含义：

状态	含义
$cur\_sp[i]$	当前在第 $i$ 个特殊点的方案数
$cur\_ordinary$	当前在任意一个普通点的方案数

若当前总方案数和是 $total$ ，那么：

转移到普通点

普通点没有额外禁止入边，只需要去掉"自己传给自己"这一种情况：

$next\_ordinary = total - cur\_ordinary$

转移到特殊点 $v$

先去掉 $v$ 自己传给自己：

$total - cur\_sp[v]$

再减掉所有被额外禁止传向 $v$ 的来源特殊点贡献。

也就是：

$next[v] = total - cur\_sp[v] - forbidden\_in\_sum[v]$

这样每一轮只需要维护：

所有特殊点
一个普通组

就能完成转移。

DP 公式

设当前所有状态方案数总和为 $total$ ，普通点单点方案数为 $curOrd$ ，特殊点 $v$ 的方案数为 $cur_v$ 。转移到普通点时，只需要去掉自己传给自己：

nextOrd=total-curOrd

转移到特殊点 $v$ 时，还要减掉所有被禁止传向 $v$ 的来源贡献：

next_v=total-cur_v-\sum_{u\to v\text{ 被禁止}} cur_u

每轮按上式更新，传完 $m$ 次后取 $1$ 号点对应状态。

公式解释：普通点完全等价，因此每个普通点可以共用一个方案数。转移到某点时，先从总方案数中去掉自己传给自己的非法情况；若目标是特殊点，还要减去题目额外禁止的来源。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int n, m, k;
vector<int> ids;
vector<pair<int, int> > edges;
vector<vector<int> > in_from; // in_from[v]：哪些特殊点不能把球传给 v
vector<long long> cur_sp, nxt_sp;
int ordinary_cnt;
int start_idx;
long long cur_ordinary, nxt_ordinary;

int get_id(int x) {
    return lower_bound(ids.begin(), ids.end(), x) - ids.begin();
}

int norm(long long x) {
    x %= MOD;
    if (x < 0) {
        x += MOD;
    }
    return (int)x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    ids.push_back(1);

    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        if (a == b) {
            // 自己传给自己本来就不允许，这种限制没有额外影响。
            continue;
        }
        edges.push_back(make_pair(a, b));
        ids.push_back(a);
        ids.push_back(b);
    }

    sort(ids.begin(), ids.end());
    ids.erase(unique(ids.begin(), ids.end()), ids.end());

    sort(edges.begin(), edges.end());
    edges.erase(unique(edges.begin(), edges.end()), edges.end());

    int sp_cnt = (int)ids.size();
    ordinary_cnt = n - sp_cnt;
    start_idx = get_id(1);

    in_from.assign(sp_cnt, vector<int>());
    for (int i = 0; i < (int)edges.size(); i++) {
        int u = get_id(edges[i].first);
        int v = get_id(edges[i].second);
        in_from[v].push_back(u);
    }

    cur_sp.assign(sp_cnt, 0);
    nxt_sp.assign(sp_cnt, 0);
    cur_sp[start_idx] = 1;
    cur_ordinary = 0;

    for (int step = 1; step <= m; step++) {
        long long total = 1LL * ordinary_cnt * cur_ordinary % MOD;
        for (int i = 0; i < sp_cnt; i++) {
            total += cur_sp[i];
            if (total >= MOD) {
                total -= MOD;
            }
        }

        for (int v = 0; v < sp_cnt; v++) {
            long long val = total - cur_sp[v];
            for (int i = 0; i < (int)in_from[v].size(); i++) {
                int u = in_from[v][i];
                val -= cur_sp[u];
            }
            nxt_sp[v] = norm(val);
        }

        nxt_ordinary = norm(total - cur_ordinary);

        cur_sp.swap(nxt_sp);
        cur_ordinary = nxt_ordinary;
    }

    cout << cur_sp[start_idx] % MOD << '\n';
    return 0;
}

复杂度

时间复杂度： $O(m \times (S + k))$ ，其中 $S$ 是特殊点个数，且 $S \leqslant 2k + 1$
空间复杂度： $O(S + k)$

总结

这题的关键不是传球本身，而是看出：

大多数球员完全等价，可以合并成一个统一状态

一旦完成这一步压缩，原本 $10^9$ 个点的问题，就变成了只和限制边数量 $k$ 有关的小规模 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P5888 传球游戏

题目背景

羊城有善蹴鞠者。会足协之杯，于校园之东北角，施两球场，蹴鞠者站球场中， $n$ 人，一球，二门，三裁判而已。观众团坐。少倾，但闻球场中哨声一响，满坐寂然，无敢哗者。

当是时，传球声，微微风声，队员疾跑声，教练呼喊声，拉拉队助威声，一时齐发，众妙毕备。满场观众无不伸颈，侧目，微笑，默叹，以为妙绝。

未几，我球员施一长传，彼球员截之，望我龙门冲来。

但见守门员 oql 立于门，若有所思——

题目描述

原来他在想这么一个问题：

场上的 $n$ 个球员围成一圈，编号从 $1$ 到 $n$ ，刚开始球在 $1$ 号球员手中。一共 $m$ 次传球，每次传球必须传给一个人，但不能传到自己手中。求第 $m$ 次传球以后传回 $1$ 号球员的方案数。

但他觉得这个问题太简单了，于是加了 $k$ 条限制，每条限制形如 $a,b$ ，表示 $a$ 号球员不能将球传给 $b$ 号球员。

为了使得 oql 的注意力转移回球场上，你需要在最短的时间内告诉他这个方案数是多少。

你只需要告诉他答案对 $998244353$ 取模后的结果。

输入格式

输入数据包括 $k+1$ 行：

第一行三个整数 $n,m,k$ ，分表代表球员数，传球次数，限制条数。

接下来 $k$ 行，每行两个整数 $a_i,b_i$ ，表示 $a_i$ 号球员不能将球传给 $b_i$ 号球员。

数据保证不会出现不同的 $i,j$ 使得 $a_i=a_j$ 且 $b_i=b_j$ 。

输出格式

输出一个整数，表示 $m$ 轮后传回 $1$ 号球员的合法方案数对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

text

12 1 0

输出 #1

text

输入输出样例 #2

输入 #2

text

13 3 0

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

1443723615

说明/提示

对于 $10\%$ 的数据， $k=0$ 。

对于另外 $15\%$ 的数据， $n\leq 500$ 。

对于另外 $20\%$ 的数据， $n\leq 5\times 10^4$ 。

对于另外 $20\%$ 的数据， $k\leq 300$ 。

对于 $100\%$ 的数据， $1\leq n\leq 10^9$ ， $0\leq m\leq 200$ ， $0\leq k \leq \min(n\times(n-1),5\times 10^4)$ ， $1\leq a_i,b_i\leq n$ ，不保证 $a_i,b_i$ 不相等。

传球游戏

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析