10.10总结

这段时间在写矩阵加速的题目，矩阵可以加速线性递推，比如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;
}

原文地址：https://blog.csdn.net/2301_80903641/article/details/142833828

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！