这段时间在写矩阵加速的题目，矩阵可以加速线性递推，比如f(n)=f(n-1)+f(n-2)可以转化为
^n
那么怎么确定转移矩阵呢，就要通过待定系数来求得，在b站的牛客竞赛有个求转移矩阵的视频，看完就可以试试这个了
P1397 [NOI2013] 矩阵游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)h
还有一种常见的用法就是邻接矩阵的k次幂，（i,j）的数字就是其他点走k步到（i,j）点的方法数（边的长度要为1）
还写了道树上dp的
总思路就是设dp[i][j],i为节点编号，j为以n为起点的余3的边的数量，那么剩下的就是排列组合的问题了，这个转移方程也蛮巧妙的，刚开始算重复了，后来把子树上的三种边分开算就a了
#include<bits/stdc++.h>
#include <iomanip>
#define ll long long
#define max_int 2147483647
#define max_ll 9223372036854775807
using namespace std;
//struct matrix{
// unsigned long long a[4][4]={0};
// void build(){
// for(int i=1;i<4;++i) a[i][i]=1;
// }
// matrix operator *(const matrix &x){
// matrix z;
// for(int k=1;k<4;++k){
// for(int i=1;i<4;++i){
// for(int j=1;j<4;++j){
// z.a[i][j]=(z.a[i][j]+a[i][k]*x.a[k][j]%m)%m;
// }
// }
// }
// return z;
// }
//};
//matrix matrixksm(matrix x,ll k){
// matrix an,bn=x;
// an.build();
// while(k){
// if(k&1) an=an*bn;
// bn=bn*bn;
// k>>=1;
// }
// return an;
//}
int n;
struct edge{
int v,w;
};
vector<edge> graph[20005];
vector<vector<int>> number(20005,vector<int>(3));
vector<int> dp(20005);
void dfs(int u){
for(auto ed:graph[u]){
dfs(ed.v);
number[u][0]+=number[ed.v][(3-ed.w)%3];
number[u][1]+=number[ed.v][(4-ed.w)%3];
number[u][2]+=number[ed.v][(5-ed.w)%3];
number[u][ed.w]++;
}
for(auto ed:graph[u]){
vector<int> a(3);
a[0]=number[ed.v][(3-ed.w)%3];
a[1]=number[ed.v][(4-ed.w)%3];
a[2]=number[ed.v][(5-ed.w)%3];
a[ed.w]++;
//cout<<u<<' '<<ed.v<<' '<<(number[u][1]-a[1])*a[2]<<' '<<(number[u][2]-a[2])*a[1]<<' '<<(number[u][0]-a[0])*a[0]+a[0]<<endl;
dp[u]+=(number[u][1]-a[1])*a[2]+(number[u][2]-a[2])*a[1]+(number[u][0]-a[0])*a[0]+a[0]*2;
}
}
int main() {
return 0;
}