题目
题目描述
有 n 个人围成一个环玩传球游戏，每轮游戏手里拿着球的那个人必须将球传给他（她）的一个朋友。游戏一共进行了 m 轮，初始球在第 a 个人手中，问游戏结束后球在第 b 个人手中的方案数。
多组测试数据。答案对 10^9+7 取模。
输入描述
第一行三个整数 Q,n,m(1≤ Q≤105,n≤200,m≤109)，含义如题目所示。
接下来 n 行，每行 n 个整数表示每个人的朋友关系，若第 i 行的第 j 个数为 0 表示 i 与 j 不是朋友，反之亦然。请特别注意本题中朋友关系是有向的。特别地，一个人不能为自己的朋友。
接下来 Q 行，每行两个整数 a,b 分别表示一组询问。
输出描述
输出共 Q 行，每行一个整数，表示答案。
示例1
输入
1 2 1
0 1
1 0
1 1
输出
0
说明
测试数据中共有两个人玩游戏。包含一组询问。
第一个人与第二个人互为朋友。游戏共进行了一轮。
第一次询问中询问游戏结束后第一个人手中仍然有球的方案数。
显然在一轮游戏后，由于每轮传球一个人必须将球传给他（她）的朋友，所以球不可能还在自己手里。
题解
知识点：线性代数，组合数学，运算优化。
众所周知，floyd可以求任意两点之间简单路径条数，因为它限制了每次走的点编号是递增的，所以不会出现回路。
但是如果把这个限制去掉，那运算过程就变成朴素的矩阵乘法，求到的东西就是任意两点之间路径条数（可以有环），就是本题需要的东西，这个过程可以用矩阵快速幂加速。
时间复杂度 \(O(n^3\log m)\)
空间复杂度 \(O(n^2)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Matrix {
const static int P;
int n, m;
vector<vector<int>> mat;
Matrix(int _n = 0) :n(_n), m(_n), mat(_n + 1, vector<int>(_n + 1)) { for (int i = 1;i <= n;i++) mat[i][i] = 1; }
Matrix(int _n, int _m) :n(_n), m(_m), mat(_n + 1, vector<int>(_m + 1)) {}
Matrix(const vector<vector<int>> &_mat) :n(_mat.size() - 1), m(_mat[1].size() - 1), mat(_mat) {}
friend Matrix operator*(const Matrix &A, const Matrix &B) {
Matrix ans(A.n, B.m);
if (A.m != B.n) return ans;
for (int i = 1;i <= A.n;i++)
for (int k = 1;k <= A.m;k++) //a.m == b.n
for (int j = 1;j <= B.m;j++)
ans.mat[i][j] = (ans.mat[i][j] + 1LL * A.mat[i][k] * B.mat[k][j]) % P;
return ans;
}
friend Matrix operator^(Matrix A, ll k) {
Matrix ans(A.n);
while (k) {
if (k & 1) ans = ans * A;
k >>= 1;
A = A * A;
}
return ans;
}
friend ostream &operator<<(ostream &os, const Matrix &A) {
for (int i = 1; i <= A.n; i++)
for (int j = 1; j <= A.m; j++)
os << A.mat[i][j] << " \n"[i != A.n && j == A.m];
return os;
}
};
const int P = 1e9 + 7;
const int Matrix::P = ::P;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q, n, m;
cin >> q >> n >> m;
Matrix A(n);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
cin >> A.mat[i][j];
A = A ^ m;
while (q--) {
int a, b;
cin >> a >> b;
cout << A.mat[a][b] << '\n';
}
return 0;
}