矩阵快速幂
有结合律的东西就能够快速幂，所以矩阵也可以快速幂。
模板
比较优美的写法是重载运算符，给一个针对方阵的实现。
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
| struct mat{
int n,p,a[N][N];
mat(int nn,int m):n(nn),p(m){memset(a,0,sizeof a);}
void init(){
for(int i=1;i<=n;i++)
a[i][i]=1;
return ;
}
int * operator[](int x){return a[x];}
const int * operator[](int x)const{return a[x];}
mat operator*(const mat &B)const{
mat res(n,p);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
(res[i][j]+=a[i][k]*B[k][j]%p)%=p;
return res;
}
mat operator+(const mat &B)const{
mat res(n,p);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
res[i][j]=(a[i][j]+B[i][j])%p;
return res;
}
void print(){
for(int i=1;i<=n;i++,cout<<"\n")
for(int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
return ;
}
};
mat qpow(mat A,int k){
mat ans=A;k--;
while(k){
if(k&1)ans=ans*A;
A=A*A,k>>=1;
}
return ans;
}
|
例题
直接分治，套矩阵快速幂即可，复杂度 ，快速幂可以预处理，优化到 。
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
| #include<bits/stdc++.h>
using namespace std;
const int N=35;
struct mat{
...
};
int n,m,k;
mat qpow(mat A,int k){
mat ans=A;k--;
while(k){
if(k&1)ans=ans*A;
A=A*A,k>>=1;
}
return ans;
}
mat a(0,0);
mat get(int k){
if(k==1)return a;
mat b=get(k/2);
b=b+qpow(a,k/2)*b;
if(k%2)b=b+qpow(a,k);
return b;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>k>>m;
a.n=n,a.p=m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
get(k).print();
return 0;
}
|
容斥原理，用总的减去没有质数的。
设 表示已经选了 个数，和 为 的方案数。
其中
对于没有质数的 同理， 只有非质数要计数。
把 预处理出来，矩阵快速幂即可。
递推式子显而易见：
运用矩阵快速幂优化，发现 会发生变化，于是拆成 18 个矩阵即可，需要注意的是矩阵乘法没有交换律，所以 18 个矩阵的顺序不能搞混。
高斯消元
例题
怎么我刚做完就降紫了qwq
简要题意：你有一个初始值为 的变量，上限为 ，定义一轮操作为：
1.若 没有达到上限， 的概率将变量加一。
2.进行 次，每次有 的概率将变量减一。
求变量变为 的期望轮数。
期望方程不难写出，但注意到 有 1500，直接高消显然会死，观察一下这个矩阵，会发现它大概长这样
1 1 0 0 0 0 ……
1 1 1 0 0 0 ……
1 1 1 1 0 0 ……
1 1 1 1 1 0 ……
会发现它的主对角线之上只有一个变量的系数不为1，因此我们可以两行两行的向下消，最后削成这个样子
1 1 0 0 0 0 ……
0 1 1 0 0 0 ……
0 0 1 1 0 0 ……
0 0 0 1 1 0 ……
0 0 0 0 1 1 ……
然后从最后一行往上消回去即可。
矩阵求逆
矩阵 的逆 为满足 ，其中 为单位矩阵
考虑直接对 做高斯消元，并且把过程中对 的所有操作，同步到单位矩阵 上，最终当 变为单位矩阵时， 会变为 的逆矩阵。
特别的，如果矩阵 无法被消元成单位矩阵，那么矩阵 没有逆矩阵。
行列式
对于任意的一个 的矩阵 ， 可视作从矩阵到数的映射。
令 表示由 个数组成的排列所构成的集合。
其中 表示 , 为排列 中的逆序对数量。
计算矩阵的行列式
直接暴力算显然不太可做。
我们考虑矩阵的基本变换会对行列式带来什么影响。
- 交换任意两行，行列式变为相反数
- 对某一行整体加上 倍另一行的值，行列式不变
那么我们直接对矩阵进行高斯消元，但是没有必要将主元化为 ，统计交换任意两行的次数。
最终结果是一个上三角矩阵，显然一个上三角矩阵的行列式 。
那么我们就在 的时间复杂度下求出了，一个矩阵的行列式。
行列式相关定理
Cauchy-Binet 定理
，通俗来讲，对于 的矩阵 和一个 的矩阵 ，相乘会得到一个 的矩阵，考虑从 中选出 列组成一个 的矩阵 ，从 中选出 行组成一个 的矩阵 ，则 就会等于所有这样的 的 det 的乘积之和。具体证明就是拆拆爆，左右两边全部拆拆拆，搞成一样的就完了。
证明中会用到一个很 nb 的trick(至少我认为): 对于形如下图的连边，我们把中间的那组点去掉，使左右两部分点直接相连，连边所产生的 边 之间的 交点 的 奇偶性 不变。(浅蓝色边为原有边，深蓝色边为新增边)
生成树计数
定义关联矩阵 $G=(g_{ij}){n\times m}g{u_i,i}=1,G_{v_i,i}=-1 A\in \R^{(n-1)\times m}n-1SA_S\sum_S{det^2(A_S)}=\text{生成树个数}A_TAdet(A)=det(A_T)det^2(A_S)=det(A_S)det(A_S^T)Cauchy-Binet$ 可得：
所以 。 注意到 。在此基础上，拉普拉斯矩阵 ,其中 为有向图 的每个点的出度的对角矩阵， 则表示邻接矩阵，如果有权就当成有 条重边。（当然，边权也可以是函数或多项式）
然后我们有 ，其中 为将 删去任意一行一列后的矩阵。
例题
容斥，钦定用那几个公司的边，跑一遍生成树计数做完了。
