当前位置: 首页 > news >正文

【学习笔记】[PA2021] Fiolki 2

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:uvw(P)。(注意这里的 P P P都是简单路径)

设起点集合为 A A A,终点集合为 B B B,大小均为 n n n

一组 A → B A\to B AB的不相交路径 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 i=j 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)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(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_{i=1}^n\omega(S_i) det(M)=S:AB(1)t(σ(S))i=1nω(Si)

其中 ∑ S : A → B \sum_{S:A\to B} S:AB表示 A → B A\to B AB的不相交路径组 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^2+mk) O(nk2+mk)

注意线性基的实现方式。

#include<bits/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 mod=1e9+7;
const int N=1e5+5;
int n,m,K,du[N],vs[N];
ll a[N][55];
mt19937 gen(114514);
vector<pair<int,int>>G[N];
queue<int>Q;
void add(ll &x,ll y){x=(x+y)%mod;
}
ll f[55][55];
int id[55];
ll res[55];
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
ll g[65];
void ins(int x){for(int i=1;i<=K;i++)g[i]=a[x][i];for(int i=1;i<=K;i++){if(g[i]){if(f[i][i]==0){for(int j=i;j<=K;j++)f[i][j]=g[j];id[i]=x;return;}if(x>id[i]){swap(x,id[i]);for(int j=i;j<=K;j++)swap(f[i][j],g[j]);}ll tmp=g[i]*fpow(f[i][i])%mod;for(int j=i;j<=K;j++)g[j]=(g[j]-f[i][j]*tmp)%mod;}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>K;for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y,z=gen()%mod;G[x].pb({y,z}),du[y]++;}for(int i=1;i<=K;i++){a[i][i]=1;}for(int i=1;i<=n;i++){if(!du[i])Q.push(i);}while(Q.size()){int u=Q.front();Q.pop();vs[u]=1;for(auto e:G[u]){int v=e.fi,w=e.se;for(int i=1;i<=K;i++)add(a[v][i],a[u][i]*w);if(--du[v]==0)Q.push(v);}}for(int i=K+1;i<=n;i++){if(vs[i])ins(i);vector<int>vec;for(int j=1;j<=K;j++)if(id[j])vec.pb(id[j]);sort(vec.begin(),vec.end());int l=K,sz=vec.size();for(int j=0;j<sz;j++){res[sz-j]+=vec[j]-l;l=vec[j];}res[0]+=i-l;}for(int i=0;i<=K;i++)cout<<res[i]<<"\n";
}
http://www.lryc.cn/news/214649.html

相关文章:

  • 计算1到100的和
  • C++下OpenMP耗时统计
  • PTA 函数题(C语言)-- 阶乘计算升级版
  • 内网穿透入门
  • Pickle pyhton反序列化
  • 动静分离技术
  • STM32单片机智能小车一PWM方式实现小车调速和转向
  • 灰狼优化算法(GWO)python
  • 项目知识点总结-住房图片信息添加-Excel导出
  • 第三届iEnglish全国ETP大赛决赛即将启动
  • 创造产业链协同优势后,凌雄科技在DaaS行业转动成长飞轮
  • 【protobuf】protobuf自定义数据格式,CMake编译C++文件读写自定义数据
  • 解决:http://localhost:8080 不在以下 request 合法域名列表中
  • Linux普通用户提权(sudo)
  • 链表指定节点的插入
  • 解决问题Conda:CondaValueError: Malformed version string ‘~’ : invalid character(s)
  • Sci Immunol丨Tim-3 适配器蛋白 Bat3 是耐受性树突状细胞
  • 天软特色因子看板(2023.10 第14期)
  • Photoshop(PS)2021版 安装教程(图文教程超详细)
  • 详解React:Props构建可复用UI的基石
  • 【Unity】【VR开发疑难】Unity运行就报无法启动XR Plugin
  • 本地启动Elasticsearch(docker启动)
  • JVM修炼印记之初识
  • 开关电源老化试验和性能检测系统软件
  • 水库大坝可视化智能远程监管方案,助力安全监测智能巡检
  • C#学习系列之虚方法和多态
  • 面试算法44:二叉树中每层的最大值
  • JWT的头部、载荷和签名分别包含哪些信息?
  • 【烧火柴问题】奇思妙想火柴
  • C++数据结构算法篇Ⅰ