什么是矩乘
一些好题
这里没什么板题，都是些比较妙的矩乘，逐步深入。
这是一个蒟蒻的刷题历程，大佬轻喷。
这里面的题目都没放代码，因为矩阵的代码一定要自己写一遍，每个人的都不一样的。
题目大意
给你很多数字：
m, a, c, x0 n, g 和一个递推式：
xn+1=(a×xn+c)%m
要你求
xn%g 的数值。
数据范围：
n,m,a,c,x0≤1018,n,m≥1,a,c,x0≥0题解
考虑暴力是很好想的，直接递推就行了。
但是显然过不了，这样的柿子就很矩乘好不。
可以令我们维护的矩阵为 :
[xic]×A=[xi+1c]
那么
A 也很好求，就是 ：
[a011]跑下矩阵快速幂就行了。
题目大意
给定一张
T 条边的无向连通图，求从
S 到
E 经过
N 条边的最短路长度。
数据范围：
1≤N≤106,1≤T≤100,1≤u,v,w≤1000题解
还是先考虑暴力，我们可以对 "经过
1≤i≤N 条边的最短路长度（全源"
那么这样会炸空间，我们考虑可以把第一位压掉，但是这样子就无法记录前面的，所以每次只能往后转移一次，也就是每次把初始的所有边都跑一遍，扩展一圈，这样跑
N 次就是答案了.
但是这样会炸空间(屁事好多),所有考虑需要这样实现(
c 的长度是
a 的长度加
b 的长度,长度是指我们枚举的
i ):
ci,j=min(ci,j,ai,k+bk,j);
这个每次转移是互不影响的,所以可以矩乘,然后就是一样的操作了.
这还是不能过!!!因为你
u,v 是可以达到
1000 的,所以你还要离散化.
题目大意
0 时刻，你从
1 号节点出发，问你
t 时刻他行走的方案数，每次他可以停在原地，移动到相邻的节点，自爆。
数据范围：
n,m≤100,t≤109题解
考虑先枚举时间，每次可以简单的
dp 一下。
那么我们肯定不可以留下一个
t 的复杂度，但是你看
n 的数据范围，这一看就很矩乘。
那就矩乘呗，和上个题一样，不过唯一要注意的是自爆操作，这个操作只要把每个点向
0 连一条边就行了，
0 没有任何出度。
题目大意
给你
a,b,c,d,n,m要你求满足以下递推式的
fn,m 是多少。
fi,j=a×fi,j−1+b (j=1)
fi,1=c×fi−1,m+d (i=1)
数据范围：
1≤n,m≤101000000,1≤a,b,c,d≤109题解
n,m 这么大，而且这个矩阵这么具有矩阵性，那就矩乘了呗。。
第一种：可以以
[fi,jb] 为初始矩阵，
[a011] 去转移。
第二种：可以以
[fi,1d] 为初始矩阵，
[c011] 去转移。
然后就很尴尬了，因为
2 种转移的初始矩阵不同。
那么在
[NOI2012] 随机数生成器中，我们是用
[xic] 作为初始矩阵，而
[a011] 是我们转移的矩阵。
但是这个你也可以变一变。可以变成用
[xi1] 作为初始矩阵，而
[ac11] 是我们转移的矩阵。
这题也是一样，可以变成这样：
第一种：可以以
[fi,j1] 为初始矩阵，
A:[ab11] 去转移。
第二种：可以以
[fi,11] 为初始矩阵，
B:[cd11] 去转移。
这也初始矩阵就相同了，接下来就是
A 用
n 列，每列用了
m−1 次，B一共用了
n−1 次。
但是不可以直接那么做，需要：
CPPA = qpow(A, m - 1), B = qpow(A * B, n - 1) * A;
Ans = Ans * B;
因为矩阵满足结合律，但是不满足交换律。
题目大意
定义一个函数
G(x) 为
1→n 的所有数首尾相接。
例如：
G(10)=12345678910求
G(n) 在膜
m 意义下的值。
数据范围：
1≤n≤1018,1≤m≤109题解
假设
fi 为
G(i) 在膜
p 的值。
那么可以找出初始矩阵
fin1 用
10k01010010 取转移即可。
显然上面的柿子不可以直接转移，而且
k 的值域是
18 ，那么我们考虑对于每个
k 取矩阵快速幂就行了。
for(A[0] = i = 1; i <= 18; ++ i) A[i] = A[i - 1] * 10;
for (i = 1; ; ++i) {
e.a[0][0] = A[i] % p;
tmp = min(n, A[i] - 1) - A[i - 1] + 1;
ans = ans * qpow(e, tmp);
if (A[i] - 1 >= n) break;
}
[NOI2012]随机数生成器