免费源码网站天,建设工程类公司网站,张家港seo建站,php网站开发案例论文Part 1
前置知识#xff1a;LGV引理
摘抄自oi-wiki#xff1a; L G V LGV LGV引理可以用来处理有向无环图上不相交路径计数等问题。
基本定义#xff1a; w ( P ) w(P) w(P)表示 P P P这条路径上所有边的 边权之积 。#xff08;路径计数时#xff0c;可以将边权都设为…Part 1
前置知识LGV引理
摘抄自oi-wiki L G V LGV LGV引理可以用来处理有向无环图上不相交路径计数等问题。
基本定义 w ( P ) w(P) w(P)表示 P P P这条路径上所有边的 边权之积 。路径计数时可以将边权都设为 1 1 1 e ( u , v ) e(u,v) e(u,v)表示 u u u到 v v v的每一条路径 P P P的 w ( P ) w(P) w(P)之和即 e ( u , v ) ∑ P : u → v w ( P ) e(u,v)\sum_{P:u\to v}w(P) e(u,v)∑P:u→vw(P)。注意这里的 P P P都是简单路径
设起点集合为 A A A终点集合为 B B B大小均为 n n n。
一组 A → B A\to B A→B的不相交路径 S S S S i S_i Si时一条从 A i A_i Ai到 B σ ( S ) i B_{\sigma(S)_i} Bσ(S)i的路径其中 σ ( S ) \sigma(S) σ(S)是一个排列对于任意 i ≠ j i\ne j ij S i S_i Si和 S j S_j Sj没有公共结点。记 t ( σ ) t(\sigma) t(σ)表示排列 σ \sigma σ的逆序对个数。
引理 M [ e ( A 1 , B 1 ) e ( A 1 , B 2 ) ⋯ e ( A 1 , B n ) e ( A 2 , B 1 ) e ( A 2 , B 2 ) ⋯ e ( A 2 , B n ) ⋮ ⋮ ⋱ ⋮ e ( A n , B 1 ) e ( A n , B 2 ) ⋯ e ( A n , B n ) ] M\begin{bmatrix} e(A_1,B_1)e(A_1,B_2)\cdotse(A_1,B_n)\\ e(A_2,B_1)e(A_2,B_2)\cdotse(A_2,B_n)\\ \vdots\vdots\ddots\vdots\\ e(A_n,B_1)e(A_n,B_2)\cdotse(A_n,B_n) \end{bmatrix} M e(A1,B1)e(A2,B1)⋮e(An,B1)e(A1,B2)e(A2,B2)⋮e(An,B2)⋯⋯⋱⋯e(A1,Bn)e(A2,Bn)⋮e(An,Bn) det(M) ∑ S : A → B ( − 1 ) t ( σ ( S ) ) ∏ i 1 n ω ( S i ) \text{det(M)}\sum_{S:A\to B}(-1)^{t(\sigma(S))}\prod_{i1}^n\omega(S_i) det(M)S:A→B∑(−1)t(σ(S))i1∏nω(Si)
其中 ∑ S : A → B \sum_{S:A\to B} ∑S:A→B表示 A → B A\to B A→B的不相交路径组 S S S。
证明考虑行列式的定义对于相交的路径组可以两两配对且符号相反因此可以抵消。
对于这道题题目保证了是有向无环图因此考虑 L G V LGV LGV引理。
显然将每条边随机赋一个权值后就可以直接通过行列式非零来判断是否存在不相交路径。
对于区间 [ l , r ] [l,r] [l,r]由于并不确定被选出的 i i i个位置因此考虑对于每个位置构造一个 k k k维向量答案即为从 [ l , r ] [l,r] [l,r]中选出的极大线性无关向量组的大小。路径权值之和可以通过拓扑排序求出。
这样我们从左往右扫描线维护一个线性基如果线性相关了就把编号最小的基替换掉将剩下的基的编号排序从小到大排序后就能知道每个区间对应的基的大小。
复杂度 O ( n k 2 m k ) O(nk^2mk) O(nk2mk)。
注意线性基的实现方式。
#includebits/stdc.h
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define inf 0x3f3f3f3f
using namespace std;
const int mod1e97;
const int N1e55;
int n,m,K,du[N],vs[N];
ll a[N][55];
mt19937 gen(114514);
vectorpairint,intG[N];
queueintQ;
void add(ll x,ll y){x(xy)%mod;
}
ll f[55][55];
int id[55];
ll res[55];
ll fpow(ll x,ll ymod-2){ll z(1);for(;y;y1){if(y1)zz*x%mod;xx*x%mod;}return z;
}
ll g[65];
void ins(int x){for(int i1;iK;i)g[i]a[x][i];for(int i1;iK;i){if(g[i]){if(f[i][i]0){for(int ji;jK;j)f[i][j]g[j];id[i]x;return;}if(xid[i]){swap(x,id[i]);for(int ji;jK;j)swap(f[i][j],g[j]);}ll tmpg[i]*fpow(f[i][i])%mod;for(int ji;jK;j)g[j](g[j]-f[i][j]*tmp)%mod;}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnmK;for(int i1;im;i){int x,y,z;cinxy,zgen()%mod;G[x].pb({y,z}),du[y];}for(int i1;iK;i){a[i][i]1;}for(int i1;in;i){if(!du[i])Q.push(i);}while(Q.size()){int uQ.front();Q.pop();vs[u]1;for(auto e:G[u]){int ve.fi,we.se;for(int i1;iK;i)add(a[v][i],a[u][i]*w);if(--du[v]0)Q.push(v);}}for(int iK1;in;i){if(vs[i])ins(i);vectorintvec;for(int j1;jK;j)if(id[j])vec.pb(id[j]);sort(vec.begin(),vec.end());int lK,szvec.size();for(int j0;jsz;j){res[sz-j]vec[j]-l;lvec[j];}res[0]i-l;}for(int i0;iK;i)coutres[i]\n;
}
