题解 P5888 传球游戏

admin

2025-08-26 08:38:39

题目链接：P5888

题面

题目背景

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

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

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

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

题目描述

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

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

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

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

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

输入格式

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

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

接下来 kkk 行，每行两个整数 ai,bia_i,b_iai,bi，表示 aia_iai 号球员不能将球传给 bib_ibi 号球员。

数据保证不会出现不同的 i,ji,ji,j 使得 ai=aja_i=a_jai=aj 且 bi=bjb_i=b_jbi=bj。

输出格式

输出一个整数，表示 mmm 轮后传回 111 号球员的合法方案数对 998244353998244353998244353 取模后的结果。

样例 #1

样例输入 #1

12 1 0

样例输出 #1

样例 #2

样例输入 #2

13 3 0

样例输出 #2

样例 #3

样例输入 #3

1234567 13 51 34 55 46 12 2

样例输出 #3

1443723615

提示

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

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

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

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

对于 100%100\%100% 的数据，1≤n≤1091\leq n\leq 10^91≤n≤109，0≤m≤2000\leq m\leq 2000≤m≤200，0≤k≤min⁡(n×(n−1),5×104)0\leq k \leq \min(n\times(n-1),5\times 10^4)0≤k≤min(n×(n−1),5×104)，1≤ai,bi≤n1\leq a_i,b_i\leq n1≤ai,bi≤n，不保证 ai,bia_i,b_iai,bi 不相等。

思路

首先看到题目，如果没有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压缩！

代码实现

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include #include #include using namespace std;#define MOD 998244353struct 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 P;int DP[2][100010];map 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++负数取模还是负数，应该将其变成正数”

小结

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