这样10分
```cpp
#include <iostream>
using namespace std;
using ll = long long;
const int kMod = 1e9 + 7;
class Matrix {
private:
public:
static const int kMaxN = 1001;
ll matrix[kMaxN][kMaxN];
ll n, m;
Matrix() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
matrix[i][j] = 0;
}
}
}
friend ostream &operator<<(ostream &out, Matrix m) {
for (int i = 1; i <= m.n; i++) {
for (int j = 1; j <= m.m; j++) {
out << m.matrix[i][j] << ' ';
}
out << '\n';
}
return out;
}
friend istream &operator>>(istream &in, Matrix &m) {
for (int i = 1; i <= m.n; i++) {
for (int j = 1; j <= m.m; j++) {
in >> m.matrix[i][j];
}
}
return in;
}
friend Matrix operator+(Matrix a, Matrix b) {
Matrix ans;
ans = a;
for (int i = 1; i <= a.n; i++) {
for (int j = 1; j <= a.m; j++) {
ans.matrix[i][j] += b.matrix[i][j];
}
}
return ans;
}
friend Matrix operator-(Matrix a, Matrix b) {
Matrix ans;
ans = a;
for (int i = 1; i <= a.n; i++) {
for (int j = 1; j <= a.m; j++) {
ans.matrix[i][j] -= b.matrix[i][j];
}
}
return ans;
}
friend Matrix operator*(Matrix a, Matrix b) {
Matrix ans;
ans.n = a.n, ans.m = b.m;
for (int k = 1; k <= a.m; k++) {
for (int i = 1; i <= a.n; i++) {
for (int j = 1; j <= b.m; j++) {
ans.matrix[i][j] = (ans.matrix[i][j] + a.matrix[i][k] * b.matrix[k][j] % kMod) % kMod;
}
}
}
return ans;
}
Matrix operator*=(Matrix a) {
*this = *this * a;
return *this;
}
Matrix operator+=(Matrix a) {
*this = *this + a;
return *this;
}
Matrix operator-=(Matrix a) {
*this = *this - a;
return *this;
}
} a;
ll b;
Matrix fPow(Matrix a, ll b) {
Matrix ans;
ans.n = ans.m = a.n;
for (int i = 1; i <= a.n; i++) {
ans.matrix[i][i] = 1;
}
while (b) {
if (b & 1) {
ans = ans * a;
}
b >>= 1;
a = a * a;
}
return ans;
}
int main() {
cin >> a.n >> b;
a.m = a.n;
cin >> a;
cout << fPow(a, b) << '\n';
return 0;
}
```
by GenesisCrystal @ 2024-02-19 10:19:39
此贴解
by GenesisCrystal @ 2024-02-19 10:49:11
@[WUYIXUAN_](/user/681755) 建议这样封装:
```cpp
struct matrix {
ll mtx[kMaxN][kMaxN];
matrix operator *(const matrix &b) const {
matrix c;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= k; ++ j) {
c.mtx[i][j] = 0;
for (int k = 1; k <= m; ++ k) {
c.mtx[i][j] = (c.mtx[i][j] + mtx[i][k] * b.mtx[k][j] % kMod) % kMod;
}
}
}
return c;
}
matrix operator ^(ll k) {
matrix ans, x = *this;
memset(ans.mtx, 0, sizeof ans.mtx);
for (int i = 1; i <= 2; ++ i) {
ans.mtx[i][i] = 1;
}
for (; k; k >>= 1, x = x * x) {
if (k & 1) {
ans = ans * x;
}
}
return ans;
}
};
```
by bc2_cryeggy @ 2024-02-19 10:49:48
@[bc2_cryeggy](/user/814343)
thx
by GenesisCrystal @ 2024-02-19 10:54:39
@[WUYIXUAN_](/user/681755) @[bc2_cryeggy](/user/814343) 建议这样封装:
```cpp
#include <iostream>
#include <climits>
#include <vector>
namespace haokee {
template<typename Ty>
class [[maybe_unused]] matrix {
private:
std::vector<std::vector<Ty>> data;
size_t height{}, width{};
public:
matrix() = default;
matrix(const matrix &other) {
height = other.height, width = other.width;
data = other.data;
}
[[maybe_unused]] matrix(size_t newHeight, size_t newWidth) {
height = newHeight;
width = newWidth;
data.resize(height, std::vector<Ty>(width, Ty()));
}
[[maybe_unused]] explicit matrix([[maybe_unused]] const std::vector<std::vector<Ty>> &vec) {
if (vec.empty() || vec.front().empty()) {
return;
}
size_t minSize = 0, maxSize = ULONG_LONG_MAX;
for (auto &v: vec) {
minSize = std::min(minSize, v.size());
maxSize = std::max(maxSize, v.size());
}
if (minSize != maxSize) {
return;
}
matrix(vec.size(), vec.front().size());
}
__attribute__((unused)) void buildStdMatrix() {
data.resize(height, std::vector<Ty>(width, Ty()));
for (size_t i = 0; i < std::min(height, width); i++) {
data[i][i] = 1;
}
}
friend std::ostream &operator<<([[maybe_unused]] std::ostream &out,
[[maybe_unused]] const matrix &x) {
for (const auto &i: x.data) {
for (auto j: i) {
out << j << ' ';
}
out << '\n';
}
return out;
}
Ty &operator()(size_t i, size_t j) {
return data[i][j];
}
size_t getHeight() {
return height;
}
size_t getWidth() {
return width;
}
};
template<typename Ty>
matrix<Ty> operator+(const matrix<Ty> &a, const matrix<Ty> &b) {
if (a.getHeight() != b.getHeight() || a.getWidth() != b.getWidth()) {
return matrix<Ty>();
}
matrix<Ty> ans(a.getHeight(), a.getWidth());
for (size_t i = 0; i < a.getHeight(); i++) {
for (size_t j = 0; j < a.getWidth(); j++) {
ans(i, j) = a(i, j) + b(i, j);
}
}
return ans;
}
template<typename Ty>
matrix<Ty> operator-(const matrix<Ty> &a, const matrix<Ty> &b) {
if (a.getHeight() != b.getHeight() || a.getWidth() != b.getWidth()) {
return matrix<Ty>();
}
matrix<Ty> ans(a.getHeight(), a.getWidth());
for (size_t i = 0; i < a.getHeight(); i++) {
for (size_t j = 0; j < a.getWidth(); j++) {
ans(i, j) = a(i, j) - b(i, j);
}
}
return ans;
}
template<typename Ty>
matrix<Ty> operator*(matrix<Ty> a, matrix<Ty> b) {
if (a.getWidth() != b.getHeight()) {
return matrix<Ty>();
}
matrix<Ty> ans(a.getHeight(), b.getWidth());
for (size_t k = 0; k < a.getWidth(); k++) {
for (size_t i = 0; i < a.getHeight(); i++) {
for (size_t j = 0; j < b.getWidth(); j++) {
ans(i, j) = (ans(i, j) + a(i, k) * b(k, j));
}
}
}
return ans;
}
template<typename Ty>
matrix<Ty> operator%(matrix<Ty> a, Ty mod) {
matrix<Ty> ans(a.getHeight(), a.getWidth());
for (size_t i = 0; i < a.getHeight(); i++) {
for (size_t j = 0; j < a.getWidth(); j++) {
ans(i, j) = a(i, j) % mod;
}
}
return ans;
}
template<typename Ty>
matrix<Ty> &operator+=(matrix<Ty> &a, matrix<Ty> b) {
a = a + b;
return a;
}
template<typename Ty>
matrix<Ty> &operator-=(matrix<Ty> &a, matrix<Ty> b) {
a = a - b;
return a;
}
template<typename Ty>
matrix<Ty> &operator*=(matrix<Ty> &a, matrix<Ty> b) {
a = a * b;
return a;
}
template<typename Ty, typename Tp>
matrix<Ty> &operator%=(matrix<Ty> &a, Tp b) {
a = a % b;
return a;
}
template<typename Ty>
__attribute__((unused)) matrix<Ty> pow(matrix<Ty> a, unsigned long long b) {
if (a.getHeight() != a.getWidth()) {
return matrix<Ty>();
}
matrix<Ty> ans(a.getHeight(), a.getWidth());
ans.buildStdMatrix();
for (; b != 0; b >>= 1) {
if (b & 1) {
ans *= a;
}
a *= a;
}
return ans;
}
template<typename Ty, typename Tp>
__attribute__((unused)) matrix<Ty> pow(matrix<Ty> a, unsigned long long b, Tp mod) {
if (a.getHeight() != a.getWidth()) {
return matrix<Ty>();
}
matrix<Ty> ans(a.getHeight(), a.getWidth());
ans.buildStdMatrix();
for (; b != 0; b >>= 1) {
if (b & 1) {
ans *= a;
ans %= mod;
}
a *= a;
}
return ans;
}
}
```
by haokee @ 2024-02-19 10:58:50
@[haokee](/user/661980) ~~建议你吗~~
by GenesisCrystal @ 2024-02-19 11:05:20
` __attribute__((unused))`
防止CLion报错
by GenesisCrystal @ 2024-02-19 11:05:49
建议这样封装:
```cpp
class node
{
public:
int n, k, a[Max][Max];
inline void fill(int x);
friend ostream &operator<<(ostream &, node &x);
friend istream &operator>>(istream &, node &x);
friend node operator*(const node &x, const node &y);
} now;
void node::fill(int x)
{
for (int i = 1; i <= this->n; i++)
{
for (int j = 1; j <= this->n; j++)
{
a[i][j] = x;
}
}
}
ostream &operator<<(std::ostream &, node &x)
{
for (int i = 1; i <= x.n; i++)
{
for (int j = 1; j <= x.n; j++)
{
cout << x.a[i][j] << " ";
}
cout << endl;
}
return cout;
}
istream &operator>>(std::istream &, node &x)
{
cin >> x.n >> x.k;
for (int i = 1; i <= x.n; i++)
{
for (int j = 1; j <= x.n; j++)
{
cin >> x.a[i][j];
}
}
return cin;
}
node operator*(const node &x, const node &y)
{
node c = x;
c.fill(0);
for (int i = 1; i <= x.n; i++)
{
for (int j = 1; j <= x.n; j++)
{
for (int o = 1; o <= x.n; o++)
{
c.a[i][j] += x.a[i][o] * y.a[o][j] % MOD;
}
c.a[i][j] %= MOD;
}
}
return c;
}
```
by fansj @ 2024-02-19 11:57:47
@[WUYIXUAN_](/user/681755)
by fansj @ 2024-02-19 11:58:05
@[fansj](/user/751264) 还要重复写,太麻烦了
by GenesisCrystal @ 2024-02-19 22:08:12