$分治算法，开篇！！$

$dfs$章节，完成

给定 $n×n$ 矩阵 $A$ 和正整数 $k$，求和 $S=A+A2+A3+…+Ak$。

输入格式
输入只包含一个测试用例。

第一行输入包含三个正整数 $n$，$k$ 和 $m$。

接下来 $n$ 行，每行包含 $n$ 个非负整数（均不超过 $32,768$），用以描绘矩阵 $A$。

输出格式
按与描述矩阵 $A$ 相同的方式，输出将 $S$ 中所有元素对 $m$ 取模后得到的矩阵。

数据范围
1≤n≤30,
1≤k≤$10^9$,
1≤m<$10^4$。
输入样例:

2 2 4
0 1
1 1

输出样例：

1 2
2 3

算法1（暴力）
看数据就知道，k<=$10^9$，暴力超时，要优化
算法2（分治优化）
构造矩阵的 (k + 1) 次方的右上角 减去 单位矩阵E 就是答案

| A E |
| 0 E | 

| A E |^2    | A^2   A + E|
| 0 E |    = | 0     E    |

| A E |^3    | A^3   A^2 + A + E|
| 0 E |    = | 0     E          |

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;

const int N = 31;

int mod, n, k;

struct Matrix {
    int n;
    vector<vector<ll>> a;

    Matrix(int x) {
        this->n = x;
        vector<vector<ll>>(x, vector<ll>(x, 0ll)).swap(a);
    }

    Matrix() {}

    Matrix operator*(const Matrix& y) {
        Matrix c(this->n);
        rep(i, 0, this->n - 1)
            rep(j, 0, this->n - 1)
                rep(k, 0, this->n - 1)
                    c.a[i][j] = (c.a[i][j] + this->a[i][k] * y.a[k][j] % mod) % mod;
        return c;
    }

}t;

Matrix qpow(Matrix a, int b) {
    Matrix ans(n << 1);
    rep(i, 0, ans.n - 1) ans.a[i][i] = 1;
    for (; b; a = a * a, b >>= 1)
        if (b & 1) ans = ans * a;
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> mod;
    t = Matrix(n << 1);
    rep(i, 0, n - 1) t.a[i + n][i + n] = t.a[i][i + n] = 1;

    rep(i, 0, n - 1)
        rep(j, 0, n - 1)
            cin >> t.a[i][j];

    t = qpow(t, k + 1);
    rep(i, 0, n - 1) t.a[i][i + n] = (t.a[i][i + n] - 1 + mod) % mod;

    rep(i, 0, n - 1) {
        rep(j, 0, n - 1) cout << t.a[i][j + n] << ' ';
        cout << '\n';
    }
    return 0;
}