怎么修改网站主页,常州做网站价位,简单的网页设计作品源码,浙江省职业能力建设处网站文章目录前言解析无向图有向图根向树叶向树code带权图code所谓矩阵树定理#xff0c;就是用矩阵解决树问题的定理。 #xff08;逃#xff09;
前言
神奇科技。 之前一直没有写博客#xff0c;觉得还是写一发比较好。 证明什么的是不可能会的 背下来背下来#xff01;
…
文章目录前言解析无向图有向图根向树叶向树code带权图code所谓矩阵树定理就是用矩阵解决树问题的定理。 逃
前言
神奇科技。 之前一直没有写博客觉得还是写一发比较好。 证明什么的是不可能会的 背下来背下来
解析
无向图
定义一个矩阵 AAA Ai,idiAi,j−#(i,j)(i≠j)A_{i,i}d_i\\A_{i,j}-\#(i,j)(i\ne j)Ai,idiAi,j−#(i,j)(ij) 其中 #(i,j)\#(i,j)#(i,j) 表示这条边的数量。 求出这个矩阵的任意一个余子式即可。
有向图
根向树
定义一个矩阵 AAA Ai,idiAi,j−#(i,j)(i≠j)A_{i,i}d_i^\\A_{i,j}-\#(i,j)(i\ne j)Ai,idiAi,j−#(i,j)(ij) 去掉第 iii 行得到的余子式就是以 iii 为根的答案。
叶向树
定义一个矩阵 AAA Ai,idi−Ai,j−#(i,j)(i≠j)A_{i,i}d_i^-\\A_{i,j}-\#(i,j)(i\ne j)Ai,idi−Ai,j−#(i,j)(ij) 唯一的区别就是主对角线从出度变成了入度为什么呢因为根的思想太陈旧已经out了
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N305;
const int mod1e97;inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;
ll a[N][N];
ll calc(int n){ll ans(1);for(int i1;in;i){for(int ji;jn;j){if(a[j][i]){if(j!i) swap(a[i],a[j]);break;}}for(int ji1;jn;j){ll da[j][i]*ksm(a[i][i],mod-2)%mod;for(int ki;kn;k) a[j][k](a[j][k]mod-a[i][k]*d%mod)%mod;}}for(int i1;in;i) ansans*a[i][i]%mod;return ans;
}
void work0(){for(int i1;im;i){int xread(),yread(),wread();if(xy) continue;(a[x][x]w)%mod;(a[y][y]w)%mod;(a[x][y]mod-w)%mod;(a[y][x]mod-w)%mod;}printf(%lld\n,calc(n-1));
}
void work1(){for(int i1;im;i){int xread(),yread(),wread();if(xy) continue;(a[y][y]w)%mod;(a[x][y]mod-w)%mod;}for(int i1;in;i){for(int j1;jn;j) a[i][j]a[i1][j1];}printf(%lld\n,calc(n-1));
}signed main(){
#ifndef ONLINE_JUDGE
// freopen(a.in,r,stdin);
// freopen(a.out,w,stdout);
#endifnread();mread();int opread();if(op0) work0();else work1();return 0;
}
/*
3
2 1 1
1 1
*/
带权图
如果一棵生成树的权值定义为边权乘积直接把边理解成边权条1权边在对应的位置加边权即可。
如果一棵生成树的权值定义为边权加和需要在矩阵内维护一个一次函数最终在 modx2\mod x^2modx2 意义下求出的行列式的一次项就是答案。 因为这就相当于单独考虑一条边的边权看它能加入多少棵生成树中。
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N35;
const int M1050;
const int S2e5100;
const int inf1e9;
const int mod998244353;inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;
int mx;
int prime[S],vis[S],tot;
ll mu[S];
void init(int n){mu[1]1;for(int i2;in;i){if(!vis[i]){prime[tot]i;mu[i]-1;}for(int j1;jtotprime[j]n/i;j){int nowprime[j];vis[i*now]1;if(i%now0){mu[i*now]0;break;}mu[i*now]-mu[i];}}for(int i1;in;i) mu[i](mu[i]mod)%mod;return;
}struct node{ll a,b;
};
node operator (const node x,const node y){return (node){(x.ay.a)%mod,(x.by.b)%mod};}
node operator - (const node x,const node y){return (node){(x.amod-y.a)%mod,(x.bmod-y.b)%mod};}
node operator * (const node x,const node y){return (node){(x.a*y.bx.b*y.a)%mod,x.b*y.b%mod};}
node operator / (const node x,const node y){ll nivksm(y.b,mod-2);return (node){(x.a*y.b-x.b*y.a%modmod)%mod*niv%mod*niv%mod,x.b*niv%mod};
}
void operator (node x,const node y){xxy;}
void operator - (node x,const node y){xx-y;}
void operator * (node x,const node y){xx*y;}
void operator / (node x,const node y){xx/y;}int u[M],v[M],w[M];
node a[N][N];
ll g[S],f[S];
void print(int n){puts(\n------\n);for(int i1;in;i){for(int j1;jn;j) printf((%lld %lld) ,a[i][j].a,a[i][j].b);puts();}
}
ll calc(int n){node ans(node){0,1};for(int i1;in;i){for(int ji1;jn;j){node da[j][i]/a[i][i];for(int ki;kn;k) a[j][k]-(a[i][k]*d);}}for(int i1;in;i){//printf( i%d a%lld ans%lld\n,i,a[i][i],ans[i])ansans*a[i][i];}return ans.a;
}
void work(int x){memset(a,0,sizeof(a));int cnt(0);for(int i1;im;i){if(w[i]%x) continue;a[u[i]][u[i]](node){w[i],1};a[v[i]][v[i]](node){w[i],1};a[u[i]][v[i]]-(node){w[i],1};a[v[i]][u[i]]-(node){w[i],1};cnt;}if(cntn-1) return;//printf(\n---x%d\n,x);//print(n);g[x]calc(n-1);//printf(ans%lld\n,g[x]);return;
}signed main() {
#ifndef ONLINE_JUDGE
// freopen(a.in,r,stdin);
// freopen(a.out,w,stdout);
#endifnread();mread();for(int i1;im;i){u[i]read();v[i]read();w[i]read();mxmax(mx,w[i]);}init(mx);for(int x1;xmx;x) work(x);ll ans(0);for(int i1;imx;i){for(int j1;j*imx;j) (f[i]g[i*j]*mu[j])%mod;(ansi*f[i])%mod;}printf(%lld\n,ans);return 0;
}
/*
3
2 1 1
1 1
*/
