当前位置：首页 > news >正文

算法提升之数论（矩阵+快速幂）

news 2025/7/30 7:53:51

通过矩阵和快速幂的方法来解决算法题目可以很好地降低时间复杂度，帮助大家更好地解决题目。

下面这道题目有一定难度，希望大家可以好好地理解，相信对大家会有很大的帮助。

问题描述

有 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是质数）
}

关于为什么可以用这个方式来表示概率：

矩阵乘法的本质是对所有可能的中间路径的概率进行 “加权求和”，这恰好符合概率转移的线性叠加规则：