算法提升之數論（矩陣+快速冪）

通過矩陣和快速冪的方法來解決算法題目可以很好地降低時間復雜度，幫助大家更好地解決題目。

下面這道題目有一定難度，希望大家可以好好地理解，相信對大家會有很大的幫助。

問題描述

有 n(2≤n≤10)?個玩家玩游戲，他們按?1?到?n?編號。第 i(1≤i≤n)?個玩家有?ti個喜歡的玩家，給出第?i個玩家喜歡的玩家的編號列表。

最初?1?號玩家拿著一朵花，游戲進行k(0≤k≤1018)?個回合，每個回合拿著花的人會把花等概率地送給自己喜歡的人之一，k?回合游戲后拿著花的人獲勝。分別求?n?個人獲勝的概率，對 109+7?取模。

輸入格式

第一行，包括兩個正整數 n,k，分別表示玩家人數和游戲輪數。

以下?n?行，每行首先有一個非負整數ti?(1≤ti?≤n)，表示第?i個玩家有?ti??個喜歡的人。然后輸入?ti??個互不相同的正整數，表示第?i個玩家喜歡的人的編號。

輸出格式

共?n?行，每行一個正整數pi?(1≤i≤n)?表示?k?次游戲后第?i?個人拿著花的概率，對109+7?取模。

令?M=109+7，可以證明所求概率可以寫成既約分數?pq??的形式，其中?p,q?均為整數且?q≡?0(modM)。應輸出整數 p×q?1(modM)。

輸入案例：

輸出案例：

代碼部分：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll p = 1e9 + 7;struct Mat
{int n, m;ll a[12][12];Mat(int x, int y, int t = 0){n = x, m = y;memset(a, 0, sizeof(a));if(t){for(int i = 0; i < min(n, m); i++)a[i][i] = 1;}}friend Mat operator * (const Mat &A, const Mat &B){Mat C(A.n, B.m, 0);for(int i = 0; i < A.n; i++)for(int j = 0; j < B.m; j++)for(int k = 0; k < A.m; k++)C.a[i][j] = (C.a[i][j] + (A.a[i][k] * B.a[k][j]) % p) % p;return C;}
};Mat qmit(Mat A, ll n)
{Mat ret(A.n, A.m, 1);while(n){if(n & 1){ret = ret * A;}A = A * A;n >>= 1;}return ret;
}ll qmit(ll a, ll b)
{ll ans = 1;while(b){if(b & 1){ans = ans * a % p;}a = a * a % p;b >>= 1;}return ans;
}ll inv(int a)
{return qmit(a, p-2);
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; ll k; cin >> n >> k;Mat X(n, n, 0), P(n, 1, 1);for(int i = 0; i < n; i++){int t; cin >> t;for(int j = 0; j < t; j++){int x; cin >> x;X.a[x-1][i] = inv(t);   // 表示花從玩家 i 到玩家 x 的概率}}P = qmit(X, k) * P;for(int i = 0; i < n; i++)cout << P.a[i][0] << '\n';return 0;
}

其中：

我們有一個游戲，規則如下：

玩家數量：共有?n?個玩家，編號從?1?到?n。
初始狀態：開始時，1?號玩家持有花朵。
回合規則：每一回合，持有花朵的玩家會等概率地將花送給自己喜歡的玩家之一。
勝利條件：經過?k?回合后，當前持有花朵的玩家獲勝。
目標：計算每個玩家在?k?回合后獲勝的概率，結果需要對?109+7?取模。

核心挑戰

問題規模：k?的最大值可以達到1018，這意味著如果我們直接模擬每一回合的傳遞過程，時間復雜度會是 O(k)，這在計算上是不可行的。
解決方案：利用矩陣快速冪（Matrix Exponentiation）技術，將時間復雜度降低到?O(log?k)。具體來說，通過矩陣乘法來表示概率的轉移過程。

矩陣表示概率轉移

1. 轉移矩陣?`X`?的定義

轉移矩陣?X?是一個?n × n?的方陣，其中?X[a][b]?表示從玩家?b?傳遞到玩家?a?的概率：

如果玩家?b?喜歡玩家?a，那么?X[a][b] = 1 / t_b，其中?t_b?是玩家?b?喜歡的人數（即玩家?b?的“出度”）。
如果玩家?b?不喜歡玩家?a，那么?X[a][b] = 0。

2. 初始概率向量?`P`

初始時只有?1?號玩家持有花朵，因此初始概率向量?P?是一個?n × 1?的列向量：

P[0][0] = 1（假設?1?號玩家對應索引?0，概率為?1）。
其余元素為?0。

矩陣快速冪的作用

概率轉移具有線性性質：k?回合后的概率分布，等于初始概率向量乘以“轉移矩陣的?k?次冪”。即：

最終概率=Xk×初始概率向量最終概率=Xk×初始概率向量

由于?k?非常大，直接計算?Xk?是不可行的。因此，我們使用矩陣快速冪技術：

將指數?k?分解為二進制形式（例如 k=2m+2n+…）。
通過?O(log?k)次矩陣乘法來計算 Xk。

數學符號的修正

在原始描述中，有一些數學符號可能無法正確顯示。以下是修正后的符號表示：

轉移矩陣?X?是一個n×n?的矩陣，其中 Xa,b??表示從玩家?b傳遞到玩家?a?的概率。
初始概率向量?P是一個n×1?的列向量，其中 P0?=1，其余 Pi?=0（假設玩家編號從?0?開始）。
最終概率的計算公式為：
最終概率=Xk?P

其中?Xk?表示矩陣?X?的?k?次冪，???表示矩陣乘法。

代碼解析：

矩陣的創建：

1. 快速創建普通矩陣（全 0）

當需要一個n×m的全 0 矩陣時，只需傳入行數和列數，第三個參數默認取 0：

Mat X(n, n);  // 等價于 Mat X(n, n, 0)，創建n×n的全0矩陣（用于轉移矩陣）

這對應代碼中初始化轉移矩陣X的場景，轉移矩陣初始時所有元素為 0，后續再根據概率填充非 0 值。

2. 快速創建單位矩陣

當需要單位矩陣（如矩陣快速冪的初始值）時，只需傳入t = 1：

Mat ret(A.n, A.m, 1);  // 創建與A同維度的單位矩陣

單位矩陣在矩陣乘法中的作用相當于數字乘法中的 “1”（任何矩陣乘以單位矩陣都等于自身），是快速冪算法的基礎。如果沒有這個參數，創建單位矩陣需要單獨寫循環初始化，代碼會更繁瑣。

1. 矩陣結構體?`Mat`

struct Mat {int n, m;  // 矩陣的行數(n)和列數(m)ll a[12][12];  // 存儲矩陣元素（n≤10，12足夠容納）// 構造函數：初始化n行m列矩陣，t=1時為單位矩陣Mat(int x, int y, int t = 0) {n = x;m = y;memset(a, 0, sizeof(a));  // 初始化為全0if (t) {  // 單位矩陣：對角線元素為1，其余為0for (int i = 0; i < min(n, m); i++) {a[i][i] = 1;}}}// 矩陣乘法：A(n×m) * B(m×p) → C(n×p)friend Mat operator*(const Mat &A, const Mat &B) {Mat C(A.n, B.m, 0);  // 結果矩陣C的大小為A的行數×B的列數for (int i = 0; i < A.n; i++) {  // 遍歷C的行for (int j = 0; j < B.m; j++) {  // 遍歷C的列for (int k = 0; k < A.m; k++) {  // 累加中間維度// 每個元素C[i][j] = sum(A[i][k] * B[k][j]) mod pC.a[i][j] = (C.a[i][j] + (A.a[i][k] * B.a[k][j]) % p) % p;}}}return C;}
};

2.矩陣快速冪?qmit(Mat A, ll n)

Mat qmit(Mat A, ll n) {Mat ret(A.n, A.m, 1);  // 初始化為單位矩陣（乘法的" identity "）while (n) {  // 二進制分解n，循環log2(n)次if (n & 1) {  // 若當前二進制位為1，將A乘入結果ret = ret * A;}A = A * A;  // A自乘，相當于指數翻倍（如A^2 → A^4 → A^8...）n >>= 1;  // 右移一位，處理下一個二進制位}return ret;
}

3.?模運算與逆元

// 快速冪計算 a^b mod p（用于求逆元）
ll qmit(ll a, ll b) {ll ans = 1;  // 結果初始為1while (b) {if (b & 1) {  // 二進制位為1時，乘入當前aans = ans * a % p;}a = a * a % p;  // a自乘，指數翻倍b >>= 1;}return ans;
}// 計算a的逆元 mod p（費馬小定理）
ll inv(int a) {return qmit(a, p-2);  // 逆元 = a^(p-2) mod p（p是質數）
}

關于為什么可以用這個方式來表示概率：

矩陣乘法的本質是對所有可能的中間路徑的概率進行 “加權求和”，這恰好符合概率轉移的線性疊加規則：

一次矩陣乘法對應一次轉移后的概率計算；
矩陣的?k?次冪對應?k?次轉移后的總概率；
最終通過初始向量與矩陣冪的乘積，得到?k?回合后的概率分布。

這就是為什么轉移概率可以用矩陣乘法表示 —— 它完美適配了 “多路徑概率疊加” 的邏輯。

一、`friend`?函數的作用：定義矩陣乘法規則

friend Mat operator*(const Mat &A, const Mat &B)?是一個友元運算符重載函數，它的核心作用是：
為?Mat?類型（矩陣）定義?*?運算符的行為，使得兩個?Mat?對象可以用?A * B?的形式進行乘法運算，就像普通整數相乘（3 * 5）一樣自然。

沒有這個函數時，A * B?會報錯（編譯器不知道如何處理兩個自定義矩陣的乘法）；有了這個函數，編譯器就會將?A * B?自動轉換為對?operator*(A, B)?的調用。