題解 P5888 傳球遊戲

發表於 分類於 閱讀次數： Waline： 文章字數： 2.8k

題目連結：P5888

題面

題目背景

羊城有善蹴鞠者。會足協之杯，於校園之東北角，施兩球場，蹴鞠者站球場中，n 人，一球，二門，三裁判而已。觀眾團坐。少傾，但聞球場中哨聲一響，滿坐寂然，無敢譁者。

當是時，傳球聲，微微風聲，隊員疾跑聲，教練呼喊聲，拉拉隊助威聲，一時齊發，眾妙畢備。滿場觀眾無不伸頸，側目，微笑，默嘆，以為妙絕。

未幾，我球員施一長傳，彼球員截之，望我龍門衝來。

但見守門員 oql 立於門，若有所思——

題目描述

原來他在想這麼一個問題：

場上的 n 個球員圍成一圈，編號從 1 到 n ，剛開始球在 1 號球員手中。一共 m 次傳球，每次傳球必須傳給一個人，但不能傳到自己手中。求第 m 次傳球以後傳回 1 號球員的方案數。

但他覺得這個問題太簡單了，於是加了 k 條限制，每條限制形如 a, b，表示 a 號球員不能將球傳給 b 號球員。

為了使得 oql 的注意力轉移回球場上，你需要在最短的時間內告訴他這個方案數是多少。

你只需要告訴他答案對 998244353 取模後的結果。

輸入格式

輸入資料包括 k + 1 行：

第一行三個整數 n, m, k，分表代表球員數，傳球次數，限制條數。

接下來 k 行，每行兩個整數 ai, bi，表示 ai 號球員不能將球傳給 bi 號球員。

資料保證不會出現不同的 i, j 使得 ai = aj 且 bi = bj。

輸出格式

輸出一個整數，表示 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 ≤ 500。

對於另外 20% 的資料，n ≤ 5 × 104。

對於另外 20% 的資料，k ≤ 300。

對於 100% 的資料，1 ≤ n ≤ 109，0 ≤ m ≤ 200，0 ≤ k ≤ min (n × (n − 1), 5 × 104)，1 ≤ ai, bi ≤ n，不保證 ai, 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壓縮！

程式碼實現

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++負數取模還是負數，應該將其變成正數”

小結

本題是一個動態規劃問題，難點在於模型的建立。