題解 P5888 傳球遊戲
題目連結：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
2 1 0
1
0
1
3 3 0
1
2
1
2
3
4
5
6
7 13 5
1 3
4 5
5 4
6 1
2 2
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){
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;
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);
}
if (!Dict[1]) P.push_back(Dict[1] = Dict.size());
int Nc = Dict.size();
int Fc = n - Nc, idf = Dict.size()+1;
int sum = 1, sum2 = 0;
DP[0][Dict[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 %= 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++負數取模還是負數，應該將其變成正數”
本題是一個動態規劃問題，難點在於模型的建立。