当前位置: 首页 > 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";
}

相关文章:

【学习笔记】[PA2021] Fiolki 2

Part 1 前置知识&#xff1a;LGV引理 摘抄自oi-wiki&#xff1a; L G V LGV LGV引理可以用来处理有向无环图上不相交路径计数等问题。 基本定义&#xff1a; w ( P ) w(P) w(P)表示 P P P这条路径上所有边的 边权之积 。&#xff08;路径计数时&#xff0c;可以将边权都设为…...

计算1到100的和

一、不好的写法 public static void main(String[] args) {int sum 0;int n 100;for (int i 1; i < n; i) {sum i;}System.out.println("sum" sum);}1.定义两个整型变量&#xff1b; 2.执行100次加法运算&#xff1b; 3.打印结果到控制台&#xff1b; 二、好…...

C++下OpenMP耗时统计

在C中&#xff0c;如果你使用OpenMP进行并行计算&#xff0c;你可以使用omp_get_wtime()函数来测量代码段的执行时间。这个函数返回一个double类型的值&#xff0c;表示从某一固定点到当前时间的秒数。因此&#xff0c;你可以在代码的开始和结束点分别调用这个函数&#xff0c;…...

PTA 函数题(C语言)-- 阶乘计算升级版

题目title&#xff1a; 阶乘计算升级版 题目作者&#xff1a; 陈越 浙江大学 本题要求实现一个打印非负整数阶乘的函数。 函数接口定义&#xff1a; void Print_Factorial ( const int N ); 其中N是用户传入的参数&#xff0c;其值不超过1000。如果N是非负整数&#…...

内网穿透入门

内网穿透 内网穿透&#xff08;英文&#xff1a;Port Forwarding&#xff09;是一种网络技术&#xff0c;用于将公共互联网&#xff08;外网&#xff09;的请求转发到私有局域网&#xff08;内网&#xff09;中的特定设备或服务。在许多情况下&#xff0c;设备或服务位于一个局…...

Pickle pyhton反序列化

参考文章 Python pickle反序列化浅析 Pickle包含四种方法 pickle.dump(obj, file) 将obj对象进行封存&#xff0c;即序列化&#xff0c;然后写入到file文件中 注:这里的file需要以wb打开(二进制可写模式) pickle.load(file) 将file这个文件进行解封&#xff0c;即反序列化 …...

动静分离技术

一、HAproxy 动静分离 1、概念&#xff1a; HAproxy 动静分离技术是一种用于优化 Web 服务器性能和提高用户体验的策略&#xff0c;它通过将动态内容和静态内容分别路由到不同的后端服务器来实现&#xff0c;减轻服务器负载&#xff0c;提高网站的响应速度。 动态内容包括由…...

STM32单片机智能小车一PWM方式实现小车调速和转向

目录 1. 电机模块开发 2. 让小车动起来 3. 串口控制小车方向 4. 如何进行小车PWM调速 5. PWM方式实现小车转向 1. 电机模块开发 L9110s概述 接通VCC&#xff0c;GND 模块电源指示灯亮&#xff0c; 以下资料来源官方&#xff0c;具体根据实际调试 IA1输入高电平&#xff…...

灰狼优化算法(GWO)python

目录 一、灰狼优化算法的python实现 二、灰狼优化算法与遗传算法的对比分析&#xff08;python&#xff09; 2.1 GWO1.py 2.2 GA1.py 2.3 GWO_vs_GA.py 2.4 运行结果 ​三、基于莱维飞行改进的灰狼优化算法的python实现 一、灰狼优化算法的python实现 import numpy as …...

项目知识点总结-住房图片信息添加-Excel导出

&#xff08;1&#xff09;住房信息添加 Controller&#xff1a; RequestMapping("/add")public String add(Home home, Model model) throws IOException{String sqlPath null;//定义文件保存的本地路径String localPath"D:\\AnZhuang\\Java项目\\选题\\Xin-…...

第三届iEnglish全国ETP大赛决赛即将启动

如今,寓教于乐的学习方式越来越受到家长和孩子的欢迎,“玩中学”成为一种既能培养兴趣又有助于孩子成长的学习趋势。 以“玩转英语,用iEnglish”为活动主题的第三届全国ETP大赛即将于本周五(11月3日)迎来总决赛的抽签仪式。据主办方iEnglish智能英语学习解决方案相关负责人称,…...

创造产业链协同优势后,凌雄科技在DaaS行业转动成长飞轮

企业服务领域&#xff0c;一直存在一种共识&#xff1a;做好很难&#xff0c;但一旦服务模式跑通了&#xff0c;得到了市场的认可&#xff0c;要滚起雪球就会事半功倍。 重资产、重运营的DaaS&#xff08;设备及服务&#xff09;赛道&#xff0c;是个非常典型的细分领域。在这…...

【protobuf】protobuf自定义数据格式,CMake编译C++文件读写自定义数据

protobuf自定义数据格式&#xff0c;CMake编译文件读写自定义数据 1.protobuf安装2.定义.proto文件3.编写main.cpp4.编写CMAkeLists配置文件5.运行 1.protobuf安装 protobuf库链接 2.定义.proto文件 新建一个Person.proto文件和一个Animal.proto文件&#xff0c;内容如下&…...

解决:http://localhost:8080 不在以下 request 合法域名列表中

在搭建资源服务器时&#xff0c;遇到了微信开发者工具中无法访问本地资源服务器的情况&#xff0c;报错如下&#xff1a; 参考一篇博文的方法&#xff0c;完美解决 【解决】http://localhost:8080 不在以下 request 合法域名列表中_localhost不在以下 request 合法域名列表中-…...

Linux普通用户提权(sudo)

文章目录 Linux普通用户提权&#xff08;sudo&#xff09;1、在sudoers文件添加普通用户2、测试 Linux普通用户提权&#xff08;sudo&#xff09; 1、在sudoers文件添加普通用户 正常来说&#xff0c;普通用户初始是不具备提权的能力的&#xff0c;比如执行sudo ls会出现报警告…...

链表指定节点的插入

向现有链表中插入结点&#xff0c;根据插入位置的不同&#xff0c;可分为以下 3 种情况&#xff1a; 插入到链表的头部&#xff0c;作为新的链表中第一个存有数据的结点&#xff08;又称为”首元结点”&#xff09;&#xff1b;插入到链表中某两个结点之间的位置&#xff1b;插…...

解决问题Conda:CondaValueError: Malformed version string ‘~’ : invalid character(s)

解决问题Conda&#xff1a;CondaValueError: Malformed version string ‘~’ : invalid character(s) 背景 今天使用Conda构建项目运行环境的时候报错&#xff1a;&#xff1a;CondaValueError: Malformed version string ‘~’ : invalid character(s) ##报错问题 在安装te…...

Sci Immunol丨Tim-3 适配器蛋白 Bat3 是耐受性树突状细胞

今天和大家分享一篇发表于2022年3月的文章&#xff0c;题目为“Tim-3 adapter protein Bat3 acts as an endogenous regulator of tolerogenic dendritic cell function”&#xff0c;发表在《Sci Immunol》杂志上。文章主要研究了Tim-3和其适配蛋白Bat3在调节免疫应答中的作用…...

天软特色因子看板(2023.10 第14期)

该因子看板跟踪天软特色因子A05005(近一月单笔流通金额占比(%)&#xff0c;该因子为近一个月单笔流通金额占比因子&#xff0c;用以刻画股票在收盘时&#xff0c;主力资金在总交易金额中所占的比重。 今日为该因子跟踪第14期&#xff0c;跟踪其在SW801160 (申万公用事业) 中的表…...

Photoshop(PS)2021版 安装教程(图文教程超详细)

软件&#xff1a;PS版本&#xff1a;2021语言&#xff1a;简体中文大小&#xff1a;2.26G安装环境&#xff1a;Win11/Win10&#xff08;1809以上版本&#xff09;硬件要求&#xff1a;CPU2.0GHz 内存4G(或更高&#xff0c;不支持7代以下CPU&#xff09;下载通道①百度网盘丨64位…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...