题解 P5888 传球游戏

发表于 分类于 阅读次数： Waline： 本文字数： 2.9k

题目链接：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

1
2 1 0

样例输出 #1

1
0

样例 #2

样例输入 #2

1
3 3 0

样例输出 #2

1
2

样例 #3

样例输入 #3

1
2
3
4
5
6
7 13 5
1 3
4 5
5 4
6 1
2 2

样例输出 #3

1
443723615

提示

对于 $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$ 不相等。

思路

首先看到题目，如果没有k限制，显然是DP。

设计状态 f[i][j] 表示第i局游戏传到j的方法数，显然满足 DP 的要求（无后效性、最优子结构等）。

得到状态转移方程：f[i][j] = sum of f[i-1][k]。其中k表示能够传到j的所有人。

但每次遍历k还是太麻烦，题目中显然能够传到j的人数大于受限人数。所以我们采用做差的方法，使用f[i][j] = sum of f[i-1][k] - f[i-1][m]，此时k表示所有人，m表示不能传球的人。所有人的方法数和可以使用一个变量记录。

但是我们发现，题目中n的范围到1e9，显然无法开这么大的数组去算。

思考发现，题中限制数很少，只有5e4，最坏情况（限制中，a、b均不同），存在约束的人数也只有1e5，剩下的是毫无限制的“自由人”，因此可以简化问题，成为“自由人”、自己（即1）和“限制人”的传球游戏。

“自由人”可以“自传球”，需要注意。而且这样做之后，编号会混乱，我们需要创建一个map重新创建编号。

还有什么优化方法？

滚动数组，可以将f压缩！

代码实现

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

#define MOD 998244353

struct Node{
    int next, to;
}NDS[100010];

int cnt = 0;
int head[100010];

void add(int a, int b){ // 表示 a 不能收到 b 的球
    NDS[cnt].to = b;
    NDS[cnt].next = head[a];
    head[a] = cnt++;
}

vector<int> P;
int DP[2][100010];

map<int, int> Dict;

int main() {
    memset(head,-1,sizeof(head));
    int n,m,k;
    cin >> n >> m >> k;
    for(int i = 1; i<=k; i++){
        int a,b;
        cin >> a >> b;
        // remap
        int ida, idb;
        if(!(ida = Dict[a])) P.push_back(Dict[a] = ida = Dict.size());
        if(!(idb = Dict[b])) P.push_back(Dict[b] = idb = Dict.size());
        if(ida != idb) add(idb,ida);
    }
    // Sp: 1 -> 可能不是限制人，但是也需要单独更新状态！
    if (!Dict[1]) P.push_back(Dict[1] = Dict.size());
    int Nc = Dict.size();
    int Fc = n - Nc, idf = Dict.size()+1;
    // 记录此次和上一次的 Sum of f
    int sum = 1, sum2 = 0;
    DP[0][Dict[1]] = 1; // 初值 -> 只能从 1 开始传球
    for(int i = 1; i<=m; i++){
        int cur = i&1; // 滚动数组
        int prev = 1-cur;
        sum2 = sum;
        sum = 0;
        for(int j : P){
            DP[cur][j] = ((sum2 - DP[prev][j])%MOD + MOD)%MOD;
            for(int x = head[j]; x!=-1; x=NDS[x].next){ // 排除不能传球的人
                int y = NDS[x].to;
                if(y==j) continue;
                DP[cur][j] = ((DP[cur][j] - DP[prev][y])%MOD + MOD) % MOD;
            }
            sum += DP[cur][j]; // 更新 sum
            sum %= MOD;
        }
        DP[cur][idf] = (1LL * sum2 * Fc % MOD - 1LL * DP[prev][idf] % MOD)%MOD; // 自传球
        sum = (sum % MOD + DP[cur][idf] % MOD) % MOD;
    }
    cout << DP[m&1][Dict[1]]%MOD << endl; // 输出结果
    return 0;
}

更多注意事项

这道题我在取模的时候调了很久 -> “C++负数取模还是负数，应该将其变成正数”

小结

本题是一个动态规划问题，难点在于模型的建立。