前言：

下定决心搞数学之后就开了个这坑。打算同时期开一下多项式（但是这俩坑啥时候填完就不晓得了），参考文献是oi-wiki

写之前翻了翻笔记本，发现很多现在觉得难的吓人的玩意寒假的时候竟然学过！！！ 但是看笔记本的字迹就知道当时反正是睡得很香了（

所以现在才来补坑），效率高的话应该还不晚

线性代数部分主要打算写一下矩阵和线性基，毕竟这俩基本是一窍不通

线性基

线性基其实就是线性空间的一组基底，使用线性基可以表示出原来的整个线性空间。

OI中常用到的是异或线性基，于是这里只介绍这一种。

下文的线性基默认为异或线性基。

说人话的话，对于一个数列而言，其线性基就是一个数的集合，取线性基中的若干数字异或起来可以得到原序列的每一个数。

线性基拥有如下性质 ：

  • 取线性基中的若干数字异或起来可以得到原序列的每一个数。
  • 线性基不能表示出 $0$，因此涉及线性基的题目如要考虑 $0$ 应当特判。
  • 线性基中数的个数唯一，且在能保证上述性质的前提下，数量最少。

实际上对于一个无限集合，其线性基的元素个数可能是无限个，但是我们在OI中很少会遇到这样的情况，于是我们只研究有限集。

于是直接看怎么构建线性基 ：

我们假设数列中的第 $i$ 个数的最高位为 $h_i$，我们的线性基数组为 $P$,原数列为 $a$。

那么对于第 $i$ 个数时，如果此时 $P_{h_i} = 0$ 那么 $P_{h_i} = a_i$,否则 $a_i = a_i \; xor \; P_{h_i}$，然后更新 $h_i$

似乎说的不是很好，可以理解为从高位到低位考虑。

这样构造出来的线性基能够表示出原数列中的所有数，这应当是显然的。

（如果觉得不显然的话可以考虑一下插入的过程然后发现反过来做一遍就可以还原出所有数。）

然后看应用。

最简单且常见的应用就是寻找异或最大值，即这个数列中各个元素相互异或所能形成的最大值。

做法就是从高位往低位考虑线性基，如果异或上当前线性基会使当前答案变大，那么就异或上，否则跳过。

这是一个看起来就很对的贪心，为了严谨证明下。

因为是从高往低扫，那么扫到第 $i$ 位的线性基如果有值，那么就可以保证这一位的值为 $1$，保证这一位为 $1$ 显然不劣，且之后不再有机会改变这一位。

查询最小值就是线性基中的最小值。

感性理解的话 ：因为异或最小值显然是有效最高位最低，那么线性基的最低位满足这个条件。

或者直接反证法 ：考虑假设存在一个异或最小值小于线性基的最小值，那么它不能被线性基表示出来（因为线性基中的最小值异或其他线性基中的数都会变大），与线性基的性质矛盾，于是不可能异或出来小于线性基最小值的数。

查询某个数能否被异或出来就尝试插入它，如果它被异或成 $0$ 那么可以表示出来，否则不能表示出来。

模板 ： P3812 【模板】线性基

然后是同样适合入门的简单例题 ： P3857 [TJOI2008]彩灯

矩阵

定义：

  1. 主对角线： 对于矩阵 $A$ ，主对角线是指 $A_{i,i}$ 的元素（左上到右下的对角线），一般用 $I$ 来表示单位矩阵，其主对角线上的元素值为 $1$ ，其余整个矩阵为 $0$

性质：

矩阵的逆：

矩阵 $A$ 的逆矩阵 $P$ 是满足 $A \times P = I$ 的矩阵
矩阵求逆可以使用高斯消元/高斯-约旦消元，具体做法为在原矩阵右侧连接一个大小相同的单位矩阵，对原矩阵进行消元成为单位矩阵后原单位矩阵就成为了原矩阵的逆矩阵。
例题是P4783,下面放一份模数为1e9+7，使用高斯-约旦消元法的代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 405
typedef long long ll;
const ll p = 1e9+7;
int n;
ll mat[N][N << 1];

ll ksm(ll ,ll );

void main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
            scanf("%lld",&mat[i][j]);
        mat[i][i+n] = 1ll;
    }

    for(int i = 1;i<=n;i++)
    {
        int mxpos = i;
        for(int j = i+1;j<=n;j++)
        if(abs(mat[j][i]) > abs(mat[mxpos][i])) mxpos = j;
        if(mxpos != i) swap(mat[i],mat[mxpos]);
        if(!mat[i][i]){
            puts("No Solution");
            return;
        }    
        ll tmp = ksm(mat[i][i],p-2);
        for(int k = 1;k<=n;k++)
        {
            if(k == i) continue;
            ll pp = mat[k][i] * tmp % p;
            for(int j = i;j <= (n << 1);j++)
            mat[k][j] = ((mat[k][j] - pp * mat[i][j]) % p + p) % p;
        }
        for(int j = 1;j<=(n << 1);j++) mat[i][j] = mat[i][j] * tmp % p;
    }

    for(int i = 1;i<=n;i++){
        for(int j = n+1;j<=(n << 1);j++)
        printf("%lld ",mat[i][j]);
        putchar('\n');
    }
}

ll ksm(ll a,ll b)
{
    ll ans = 1;
    for(;b;b>>=1,a = a * a % p) if(b & 1) ans = ans * a % p;
    return ans;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

矩阵运算：

加减法：

对应位置相加减（莫得例题）。

矩阵乘法：

1.定义：

设矩阵 $A$ 乘以矩阵 $B$ 得到矩阵 $C$ ，那么矩阵 $C$ 中第 $i$ 行第 $j$ 列的元素，就是由矩阵 $A$ 的第 $i$ 行每个元素分别与矩阵$B$ 的第 $j$ 列的每个元素对应相乘再相加得到的。形式化的表达就是：
对于 $P \times M$ 的矩阵 $A$ 和 $M \times Q$ 的矩阵 $B$ ，定义 $C = A \times B$，则有：

2.性质：

满足结合律，不满足交换律（甚至交换后不一定能进行矩阵乘法）

3.优化：

通常使用矩阵快速幂进行优化。
例题为P3390，下面放一个用重载运算符实现的冗长的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
#define RE return 0
#define N 110
const ll mod = 1e9 + 7;
ll n,k;
struct matrix{
    
    ll a[N][N];
   
    matrix(int n1,int k1) {memset(a,0,sizeof(a));}
    void init(){for(int i = 1;i<=n;i++) a[i][i] = 1;}

    friend matrix operator + (const matrix &A,const matrix &B)
    {
        matrix ans(n,k);
        for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++) 
        ans.a[i][j] = A.a[i][j] + B.a[i][j] % mod;
        return ans;
    }

    friend matrix operator - (const matrix &A,const matrix &B)
    {
        matrix ans(n,k);
        for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
        ans.a[i][j] = A.a[i][j] - B.a[i][j];
        return ans;
    }

    friend matrix operator * (const matrix &A,const matrix &B)
    {
        matrix ans(n,k);
        for(int k = 1;k<=n;k++)
        for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
        ans.a[i][j] = (ans.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
        return ans;
    }

    matrix ksm(matrix a,long long b)
    {
        matrix ans(n,k);
        ans.init();
        for(;b;b >>= 1,a = a * a) if(b & 1) ans = ans * a;
        return ans;
    }
    // matrix ksm()
    // {
    //     matrix ans(n,k);
    //     ll b = k;
    //     for(;b;b >>= 1,a = a * a) if(b & 1) ans = ans * a;
    //     return ans;
    // }

    friend ostream &operator << (ostream &, matrix &A)
    {
        for(int i = 1;i<=n;i++)
        {
            for(int j = 1;j<=n;j++)
            cout<< A.a[i][j] << ' ';
            cout<<'\n';
        }
        return cout;
    }

    friend istream & operator >> (istream &,matrix &A)
    {
        for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
        // scanf("%lld",A.a[i][j]);
        cin >> A.a[i][j];
        return cin;
    }
};

int main()
{
    scanf("%lld%lld",&n,&k);
    matrix a(n,k);
    cin>>a;
    matrix b(n,k);
    b = a.ksm(a,k);
    cout << b;
    RE;
}

}

int main()
{
    return Pozhu :: main();
}

重载了流式输入输出所以写起来舒服（或许并没有）一些

矩阵应用：

（持续更新）
比较简单也常见的大概是

矩阵加速递推

最经典的是矩阵加速递推斐波那契数列，可以做到1e18的级别（当然再高可以去生成函数那边搞通项公式来降维打击不过至少得套个高精板子所以我很不愿意写）

因为矩阵加速递推我寒假的时候 睡着觉 积极听课来着，所以下边的东西是总结的时候现学现卖 理解性抄写oi-wiki 的：

矩阵加速递推最难的部分在于构造矩阵（毕竟矩阵快速幂知道定义就会写）

设一个矩阵$F_{ib}(n)$表示一个$1 \times 2 $的矩阵$[F_n,F_{n-1}]$，那么我们希望通过 $F_{ib}(n-1)$ 推出 $F_{ib}(n)$ 来达到递推的目的。

我们尝试构造一个矩阵，使其右乘（放到右边相乘） $F_{ib}(n-1)$ 得到 $F_{ib}(n)$ 以实现递推。

（看到这里建议停下来根据前边的定义自己推导一下这个矩阵，并不难做到。我写的时候花一分钟推完之后觉得不难）

显然我们有 $ C = F_{ib}(n) = [F_n,F_{n-1}]$ , $A = F_{ib}(n-1) = [F_{n-1},F_{n-2}]$
那么我们就要保证

且

考虑矩阵乘法的定义，易得：

矩阵$B$应当有两列以支持矩阵乘法，
其中$A$的第一行（只有一行）两个元素乘$B$的第一列之作和得到的是 $C_{1,1}$，值应该是 $A_{1,1} + A_{1,2}$，那么显然矩阵 $B$ 的第一列两个元素都为 $1$ 。

同理， $A$ 的第一行两个元素乘完 $B$ 的第二列之后得到的结果 $C_{1,2} $ 值应该是 $A_{1,1}$ ，这就说明乘法过程中 $A_{1,2}$ 乘上了 $0$ 从而没有贡献。 那么 $B$ 的第二列元素就应该是 $1,0$ （实际上应该竖着写。

那么我们完成了构造，矩阵 $B$ 就是 ：

求解时，前两项是已知项，不需进行矩阵加速，后边的第$n$项就是 $Fib_{2}$ 乘上 $n-2$ 个矩阵 $B$ 得到的矩阵的第一个元素，根据矩阵乘法的结合律我们可以使用矩阵快速幂来优化这一过程。

这道题就是P1962
（我没写过代码而且写一份的话就太长了而且所有板子上边都有所以我就不放代码了）

所以这个经典例题是很简单的，oi-wiki上还有一些更复杂的例子，但是给出的说明比较简略。
后边如果有时间的话回去看看然后补个详细说明。还有几种应用也一并咕了（new post：鸽子的咕咕列表）(8.12 前来补坑) ：

更复杂一点的例子是：

这个柿子看起来比较一般，可拓展性也比较强。

我们考虑用什么来表达当前的状态。

由这个递推式的定义，我们有：

如果仅仅使用这样的矩阵：

显然是不能满足需要的，因为我们用这样的矩阵不能通过矩阵乘法得到我们需要的常数项和3的幂

于是我们自然而然地考虑在表达状态的矩阵中添加这些内容，那么我们的矩阵就应当是：

这个矩阵已经可以满足我们的需要，接下来考虑构造转移矩阵，由矩阵乘法的定义和上文提到的思想，读者应当尝试自己构造一下这个矩阵（我就是看到这之后自己写出来的，很简单）

首先显然我们的转移矩阵应当有5列。对于矩阵乘法的更加直观的想法就是把基础矩阵以右端点为轴顺时针旋转90°，然后放到转移矩阵的每一列上，来得到我们结果的对应列。

显然我们的转移矩阵应该是一个方阵 $(n \times n)$ ，原因可以这样简单解释： 首先我们的状态矩阵乘上转移矩阵后的结果矩阵形式上应当和状态矩阵相同，因此转移矩阵的列数和行数应该相同；其次我们需要运用结合律加速递推，所以转移矩阵必须能自己和自己相乘，那么由定义可知它必须是方阵。

那么构造过程对应递推式凑系数就好，这里放一下结果：

于是我们可以解决较为一般的矩阵加速递推问题了。

矩阵表达修改

例题是P7453 THUSCH2017 大魔法师

题面就不放了，大抵是一个水晶球$i$有三种属性 $A_i,B_i,C_i$ ，要维护的操作是对于一个区间的水晶球，略有些意思但也很简单的是以下三个区间操作：

我们的状态矩阵是：

对于其中A的操作，我们的转移矩阵就是

对于B操作，我们的转移矩阵就是

对于C操作，我们的转移矩阵就是

由于矩阵乘法具有结合律和分配律，所以对于区间内每个矩阵单点修改的和就是对于区间的和进行单点修改。那么区间修改的问题就完成了，我们可以考虑使用线段树来维护这一修改。

所以剩下的问题就是套一个矩阵板子和线段树维护区间乘和求和操作的板子，理论难度没了，实现细节的话第一次实现会有很多注意不到的地方。矩阵从0开始存似乎要比从1开始快一些，但是我从1开始也能在C98+O2的条件下不写卡常地卡过这题（这题比较卡常）。一些简单的卡常优化是：

  • 矩阵从0开始存
  • 记录每个节点是否有 lazytag ，只在有 lazytag 的节点进行 push_down
  • 对于叶子节点，不需要进行 push_down
    然后就可以跑的飞快了（

放代码的话就是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define SIZE 5
#define N 250010
const int mod = 998244353;
struct matrix
{
    int n,m;
    int a[SIZE][SIZE];

    void init(){ memset(a,0,sizeof(a));}
    void bas(){for(int i = 1;i<=n;i++) a[i][i] = 1;}
    matrix(){n = 4,m = 4;}
    matrix(int _n,int _m):n(_n),m(_m){init();}
    matrix(int _n,int _m,const int _a[SIZE][SIZE]):n(_n),m(_m)
    {
        for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
        a[i][j] = _a[i][j];
    }
    friend matrix operator * (matrix a,matrix b)
    {
        matrix ans(a.n,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.a[i][j] = (ans.a[i][j] + 1ll * a.a[i][k] * b.a[k][j] % mod) % mod;
        return ans;
    }
    friend matrix operator + (matrix a,matrix b)
    {
        for(int i = 1;i<=a.n;i++)
        for(int j = 1;j<=a.m;j++)
        {
            a.a[i][j] += b.a[i][j];
            if(a.a[i][j] > mod) a.a[i][j] -= mod;
        }
        return a;
    }
    friend matrix operator - (matrix a,matrix b)
    {
        for(int i = 1;i<=a.n;i++)
        for(int j = 1;j<=a.m;j++)
        {
            a.a[i][j] -= b.a[i][j];
            if(a.a[i][j] < 0) a.a[i][j] += mod;
        }
        return a;
    }
};

struct Tree{
    int l,r;
    bool have_lz;
    matrix sum;
    matrix lz;
}t[N << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

const int a_b[SIZE][SIZE] = {
{0,0,0,0,0},
{0,1,0,0,0},
{0,1,1,0,0},
{0,0,0,1,0},
{0,0,0,0,1},
};
const int b_c[SIZE][SIZE] = {
{0,0,0,0,0},
{0,1,0,0,0},
{0,0,1,0,0},
{0,0,1,1,0},
{0,0,0,0,1},
};
const int c_a[SIZE][SIZE] = {
{0,0,0,0,0},
{0,1,0,1,0},
{0,0,1,0,0},
{0,0,0,1,0},
{0,0,0,0,1},
};

const matrix A_B = (matrix){4,4,a_b};
const matrix B_C = (matrix){4,4,b_c};
const matrix C_A = (matrix){4,4,c_a};

int n,m;
matrix all_use(4,4);
int sta_a[N],sta_b[N],sta_c[N];

void push_up(int );
void push_down(int );
matrix ksm(matrix ,int );
void build(int ,int ,int );
matrix query(int ,int ,int );
void change(int ,int ,int ,int ,int );

void main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    scanf("%d%d%d",&sta_a[i],&sta_b[i],&sta_c[i]);
    build(1,1,n);
    scanf("%d",&m);
    int l,r,op,v;
    for(int i = 1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op >= 4 && op <= 6) scanf("%d",&v);
        if(op < 7) change(1,l,r,op,v);
        else {
            matrix ans(1,4);
            ans = query(1,l,r);
            printf("%d %d %d\n",ans.a[1][1],ans.a[1][2],ans.a[1][3]);
        }
    }
    return;
}

matrix query(int x,int l,int r)
{
    if(t[x].l >= l && t[x].r <= r) return t[x].sum;
    push_down(x);
    matrix ans(1,4);
    if(t[ls(x)].r >= l) ans = ans + query(ls(x),l,r);
    if(t[rs(x)].l <= r) ans = ans + query(rs(x),l,r);
    return ans;
}

void change(int x,int l,int r,int type,int v)
{
    if(t[x].l >= l && t[x].r <= r)
    {
        t[x].have_lz = 1;
        if(type == 1){t[x].sum = t[x].sum * A_B;t[x].lz = t[x].lz * A_B;return;}
        if(type == 2){t[x].sum = t[x].sum * B_C;t[x].lz = t[x].lz * B_C;return;}
        if(type == 3){t[x].sum = t[x].sum * C_A;t[x].lz = t[x].lz * C_A;return;}
        if(type == 4)
        {
            all_use.init(),all_use.bas();
            all_use.a[4][1] = v;
            t[x].sum = t[x].sum * all_use;
            t[x].lz = t[x].lz * all_use;
            return;
        }
        if(type == 5)
        {
            all_use.init(),all_use.bas();
            all_use.a[2][2] = v;
            t[x].sum = t[x].sum * all_use;
            t[x].lz = t[x].lz * all_use;
            return;
        }
        if(type == 6)
        {
            all_use.init(),all_use.bas();
            all_use.a[3][3] = 0;
            all_use.a[4][3] = v;
            t[x].sum = t[x].sum * all_use;
            t[x].lz = t[x].lz * all_use;
            return;
        }
    }
    push_down(x);
    if(t[ls(x)].r >= l) change(ls(x),l,r,type,v);
    if(t[rs(x)].l <= r) change(rs(x),l,r,type,v);
    push_up(x);
}

void build(int x,int l,int r)
{
    t[x].l = l,t[x].r = r;
    t[x].lz.bas();
    t[x].have_lz = 0;
    if(l == r)
    {
        t[x].sum.n = 1,t[x].sum.m = 4;
        t[x].sum.a[1][1] = sta_a[l];
        t[x].sum.a[1][2] = sta_b[l];
        t[x].sum.a[1][3] = sta_c[l];
        t[x].sum.a[1][4] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    push_up(x);
}

void push_down(int x)
{
    if(!t[x].have_lz) return;
    if(t[x].l == t[x].r) return;
    t[ls(x)].have_lz = t[rs(x)].have_lz = 1;
    t[ls(x)].sum = t[ls(x)].sum * t[x].lz;
    t[rs(x)].sum = t[rs(x)].sum * t[x].lz;
    t[ls(x)].lz = t[ls(x)].lz * t[x].lz;
    t[rs(x)].lz = t[rs(x)].lz * t[x].lz;
    t[x].lz.init();t[x].lz.bas();t[x].have_lz = 0;
}

void push_up(int x)
{
    t[x].sum = t[ls(x)].sum + t[rs(x)].sum;
}

matrix ksm(matrix a,int b)
{
    matrix ans(a.n,a.m);
    ans.bas();
    for(;b;b>>=1,a = a * a) if(b & 1) ans = ans * a;
    return ans;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

（为了便于理解，代码中矩阵是从1开始存的。敲了个快速幂但是实际上没用）

于是我们解决了普通的矩阵表达修改问题。

定长路径统计

给定一个 $n$ 阶有向图（每条边的边权都是1）和一个整数 $k$ ， 对于所有点对 $(u,v)$ 求出从
$u$ 到 $v$ 长度为 $k$ 的路径的数量（不一定是简单路径，即可以重复经过同一个点或边）。

我们选择使用邻接矩阵 $(G)$ 来存图（此处略去邻接矩阵的定义），其中若有重边，邻接矩阵中对应位置的值为重边条数。

这一算法适用于有重边和自环的图。

我们考虑矩阵最大的优势在于它可以快速幂它可以快速递推——用快速幂可以把递推的时间复杂度降到$log$级别。于是我们回头看我们已有的信息：发现我们已有的邻接矩阵恰好是 $k = 1$ 时的状态！

设长度为 $k$ 的路径条数构成的（邻接）矩阵为 $C_i$

于是考虑递推，运用一点点类似最短路或DP的思想我们得到 ：

这和矩阵乘法的定义式如出一辙。所以我们将其看作矩阵乘法，那么我们的递推式也就可以立即得出 ：

于是我们显然有 ：

那么问题解决了，这个做法的时间复杂度是 $O(n^3\log k)$

对应的模板题是AT4539

定长最短路

给定一个 $n$ 阶加权有向图和一个整数 $k$ ， 对于所有点对 $(u,v)$ 求出从
$u$ 到 $v$ 恰好包含 $k$ 条边的最短路径的长度（不一定是简单路径）。

和上一个问题类似地，我们使用邻接矩阵 $G$ 来存图，但是这次矩阵内存储的信息不再是边数而是边权，就像是我们在学习最短路算法地入门时做的那样——对于没有边的位置，我们把它的值赋为 $ \infty $。

显然我们拥有的状态又是 $k=1$ 时的答案。那么转移方程依然是容易得到的 ：

这个式子和矩阵乘法的形式类似，只是将乘积求和转变成了相加取最小值的过程，实现上我们仅需要略微改变乘号的重载过程即可，如果我们定义这个运算为 $\odot$ ，即 ：

那么我们的递推式就是 ：

由于 $\odot$ 运算显然满足结合律，我们就有 ：

时间复杂度依然是 $O(n^3\log k)$ ，我们解决了这个问题。

限长路径计数/最短路

给定一个 $n$ 阶有向图，边权为 $1$ ，和一个整数 $k$ 。对于每个点对 $(u,v)$ 找到从 $u$ 到 $v$ 长度小于等于 $k$ 的路径的数量（不一定是简单路径）。

我们对于定长路径计数的邻接矩阵稍作修改 ：

我们对每个点都加一个权值为 $1$ 的自环，这样我们每次转移（乘法）的时候就都会考虑走自环（原地不动）的情况，也就是小于 $k$ 的情况

同样的思想我们可以解决边数小于等于 $k$ 的最短路，即加一个边权为 $0$ 的自环

所以到现在都没碰到难的吓人的东西（但是oi-wiki上只给到这里。后边考虑再补，先写到这罢。