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

【学习笔记】LOJ #6240. 仙人掌

毒瘤题😅

简单版本 CF235D Graph Game

首先,考虑建立圆方树,然后对于一个点双(简单环)上的两个点,有两条路径可以到达

和简单版本类似,考虑容斥。即枚举点对 i , j i,j i,j之间 哪些路径是联通的 ,记固定下来的路径的并为 A A A,则 i , j i,j i,j之间通过 A A A联通的概率为 1 ∣ A ∣ \frac{1}{|A|} A1

然后就是神来之笔了:设 A A A中有 c n t cnt cnt个环,则容斥系数为 ( − 1 ) c n t (-1)^{cnt} (1)cnt。证明:考虑 i , j i,j i,j之间实际有 k k k个环,则这个方案被计算了 ∑ x ≤ k 2 x ( k x ) ( − 1 ) k − x = ( 2 − 1 ) k = 1 \sum_{x\le k}2^x\binom{k}{x}(-1)^{k-x}=(2-1)^k=1 xk2x(xk)(1)kx=(21)k=1次。

考虑在圆方树上 D P DP DP。因为点对之间的 L C A LCA LCA可能是方点或者圆点,因此不好统计。可以考虑直接枚举其中一个点,然后跑 D F S DFS DFS,复杂度 O ( n 3 ) O(n^3) O(n3)

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define db double
using namespace std;
const int mod=998244353;
const int N=805;
int n,m,tot;
vector<int>G[N];
int dfn[N],low[N],ps[N][N],num;
ll res;
stack<int>s;
vector<int>G2[N];
void tarjan(int u){low[u]=dfn[u]=++num,s.push(u);for(auto v:G[u]){if(!dfn[v]){tarjan(v),low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){int tmp=0,d=0;tot++,G2[u].pb(tot),G2[tot].pb(u),ps[tot][u]=d++;do{tmp=s.top(),s.pop();G2[tot].pb(tmp),G2[tmp].pb(tot),ps[tot][tmp]=d++;}while(tmp!=v);}}else low[u]=min(low[u],dfn[v]);}
}
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 f[N][N],fac[N],inv[N],invnum[N];
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;for(int i=1;i<=n;i++)invnum[i]=inv[i]*fac[i-1]%mod;
}
void add(ll &x,ll y){x=(x+y)%mod;
}
int sz[N];
void dfs(int u,int topf,int sz){for(int i=1;i<=sz;i++){if(f[u][i])add(res,invnum[i]*f[u][i]);}for(auto e:G2[u]){if(e==topf)continue;for(int i=0;i<G2[e].size();i++){if(i==ps[e][u])continue;int v=G2[e][i],l1=abs(ps[e][u]-ps[e][v])-1,l2=G2[e].size()-2-l1;for(int i=1;i<=sz;i++){add(f[v][i+l1+1],f[u][i]);add(f[v][i+l2+1],f[u][i]);add(f[v][i+l1+l2+1],-f[u][i]);}dfs(v,e,sz+l1+l2+1);}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m,init(n),tot=n;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;G[x].pb(y),G[y].pb(x);}tarjan(1);for(int i=1;i<=n;i++){memset(f,0,sizeof f),f[i][1]=1,dfs(i,-1,1); }cout<<(res+mod)%mod;
}

相关文章:

【学习笔记】LOJ #6240. 仙人掌

毒瘤题&#x1f605; 简单版本 CF235D Graph Game 首先&#xff0c;考虑建立圆方树&#xff0c;然后对于一个点双&#xff08;简单环&#xff09;上的两个点&#xff0c;有两条路径可以到达 和简单版本类似&#xff0c;考虑容斥。即枚举点对 i , j i,j i,j之间 哪些路径是联…...

java通过接口转发文件(上传下载)

java接口转发上传的文件 RequestMapping(value "/XXXX/fileUpload", method RequestMethod.POST) public String getFileUpload2(RequestParam("file") MultipartFile file, HttpServletRequest request) public static String hotMapPost3(String ur…...

Docker-部署docker-compose以及管理服务

部署docker-compose以及管理服务 文章目录 部署docker-compose以及管理服务[TOC] 前言一、docker-compose是什么&#xff1f;1、介绍2、 功能 二、安装docker-compose1.yum直接安装2.二进制安装3.pip安装 三、docker-compose部署服务1.编写docker-compose.yml文件 总结 前言 D…...

Android - Monkey 测试应用出现Crash报错IllegalStateException

问题描述 平时使用Lottie动画都是正常的&#xff0c;没出过这个crash问题&#xff0c;看下的报错信息&#xff0c;代码中文件夹也设置了&#xff0c;没看出来问题。 AndroidRuntime: java.lang.IllegalStateException: You must set an images folder before loading an imag…...

Spring源码分析 事务 实现原理

文章目录 什么是事务Spring事务管理Spring事务实现原理事务管理器事务定义事务的开启事务核心方法业务代码使用事务TransactionInterceptor 什么是事务 一般所指的事务是数据库事务&#xff0c;是指一批不可分割的数据库操作序列&#xff0c;也是数据库并发控制的基本单位。其…...

ADS-B及雷达显示终端8.3

新版本功能升级主要有如下: 1、地图更新 在上一版本8.2中使用的高程地图为由SRTM经过地形晕渲后&#xff0c;生成地形图片&#xff0c;然后对图片进行贴图&#xff0c;一一按规定位置、大小将地形图贴至底图上&#xff0c;而后在底图上进行二维矢量地图的绘制&#xff0c;包括…...

第二章:最新版零基础学习 PYTHON 教程(第二节 - Python 输入/输出–从 Python 控制台获取输入)

目录 Python 中的控制台是什么? 接受来自控制台的输入: 1. 将输入类型转换为整数:...

linux安装配置 flume

目录 一 解压安装包 二 配置部署 &#xff08;1&#xff09;修改配置 &#xff08;2&#xff09;下载工具 &#xff08;3&#xff09;创建配置文件 &#xff08;4&#xff09;启动监听测试 &#xff08;5&#xff09;flume监控文件 一 解压安装包 这里提供了网盘资源 链…...

SSM - Springboot - MyBatis-Plus 全栈体系(十五)

第三章 MyBatis 二、MyBatis 基本使用 4. CRUD 强化练习 4.1 准备数据库数据 首先&#xff0c;我们需要准备一张名为 user 的表。该表包含字段 id&#xff08;主键&#xff09;、username、password。创建SQL如下&#xff1a; CREATE TABLE user (id INT(11) NOT NULL AUT…...

win10默认浏览器改不了怎么办,解决方法详解

win10默认浏览器改不了怎么办&#xff0c;解决方法详解_蓝天网络 在使用Windows 10操作系统时&#xff0c;你可能会遇到无法更改默认浏览器的情况。这可能是因为其他程序或设置正在干扰更改。如果你也遇到了这个问题&#xff0c;不要担心&#xff0c;本文将为你提供详细的解决…...

C语言连接MySQL并执行SQL语句(hello world)

1.新建一个控制台项目 参考【VS2022 和 VS2010 C语言控制台输出 Hello World】VS2022 和 VS2010 C语言控制台输出 Hello World_vs2022源文件在哪_西晋的no1的博客-CSDN博客 2.安装MySQL 参考【MySQL 8.0.34安装教程】MySQL 8.0.34安装教程_西晋的no1的博客-CSDN博客 3.复制MySQ…...

react实现动态递增展示数字特效

在可视化展示界面时有一种场景&#xff0c;就是页面在初始化的时候&#xff0c;有些数字展示想要从某个值开始动态递增到实际值&#xff0c;形成一种动画效果。例如&#xff1a; 写一个数字递增的组件&#xff0c;有两种方式&#xff1a;1.固定步长&#xff0c;代码如下&#x…...

读取.nrrd和.dcm文件格式医学图片可视化与预处理

nrrd数据格式 MITK默认会将医学图像保存为格式为NRRD的图像&#xff0c;在这个数据格式中包含&#xff1a; 1、一个单个的数据头文件&#xff1a;为科学可视化和医学图像处理准确地表示N维度的栅格信息。 2、既能分开又能合并的图像文件。 nrrd_options输出 {u’dimension’:…...

VS CODE中的筛选器如何打开?

最近更新了vscode1.82版本&#xff0c;发现在git管理界面有一个“筛选器”功能&#xff0c;十分好用&#xff0c;后来关掉了&#xff0c;找了好久都没有找到办法打开这个筛选器功能&#xff0c;今天无意中不知道按到了哪个快捷键&#xff0c;打开了&#xff0c;就是下图这个&am…...

vue 多环境文件配置(开发,测试,生产)

1.经常我们在开发时候会有不同环境&#xff0c;要代理的路由等等都会出现不同 配置一下三个文件打包的时候&#xff0c;执行三个不同的指令就会打包不同的环境 npm run build:dev npm run build:test npm run build:prodpackage.json 中配置scripts 指令 以,env.development…...

在服务器上搭建pulseaudio的运行环境,指定其运行目录、状态目录和模块目录

如果想在搭建 PulseAudio 的服务器上指定其运行目录、状态目录和模块目录&#xff0c;可以通过修改 PulseAudio 的配置文件来实现。一般情况下所涉及的配置文件和相关选项如下所示&#xff1a; 1、配置文件路径&#xff1a;通常情况下&#xff0c;PulseAudio 的配置文件位于 /…...

[Qt]QListView 重绘实例之一:背景重绘

0 环境 Windows 11Qt 5.15.2 MinGW x64 1 系列文章 简介&#xff1a;本系列文章&#xff0c;是以纯代码方式实现 Qt 控件的重构&#xff0c;尽量不使用 Qss 方式。 《[Qt]QListView 重绘实例之一&#xff1a;背景重绘》 《[Qt]QListView 重绘实例之二&#xff1a;列表项覆…...

国庆周《Linux学习第二课》

Linux开篇指南针环境安装(第一课)-CSDN博客 Linux详细的环境安装介绍在上面 第一 环境准备过程 安装过程...

6年前的麒麟980依旧可以再战

麒麟980&#xff0c;使用6年后的今天&#xff0c;我对它进行跑分测试。 在bench旗下的VRMark跑分中&#xff0c;麒麟980荣获5023分&#xff0c;同款跑分APP&#xff0c;要知道同一时期的高通骁龙855只有4937分&#xff0c; 打游戏&#xff0c;以和平精英为例&#xff0c;帧率3…...

JS计算任意多边形的面积

计算任意多边形的面积需要使用一些几何数学公式。具体的计算方法取决于多边形的形状和提供的顶点坐标。下面是一个通用的 JavaScript 函数&#xff0c;用于计算任意多边形的面积&#xff0c;假设你提供多边形的顶点坐标数组&#xff1a; function calculatePolygonArea(vertic…...

工业视觉杂散物检测系统方案设计

构建一套完整可靠的工业视觉检测系统&#xff0c;核心在于将其无缝嵌入到现有的装配流程中。下面是一个从系统架构部署、执行标准、再到具体模块技术选型的完整实施方案&#xff0c;希望能帮你构建一套精准且高效的检测闭环。 &#x1f3d7;️ 系统总体架构 一个完整的检测系统…...

Avogadro 2:3分钟掌握跨平台分子建模的5大核心价值

Avogadro 2&#xff1a;3分钟掌握跨平台分子建模的5大核心价值 【免费下载链接】avogadroapp Avogadro is an advanced molecular editor designed for cross-platform use in computational chemistry, molecular modeling, bioinformatics, materials science, and related a…...

乔布斯产品哲学对硬件工程师的启示:从参数到体验的转变

1. 项目概述&#xff1a;一次对乔布斯遗产的技术性致敬2011年10月6日&#xff0c;当史蒂夫乔布斯逝世的消息传来&#xff0c;整个科技界陷入了一种复杂的情绪。作为一名长期在电子工程与消费电子领域工作的人&#xff0c;我的感受尤为深刻。那天&#xff0c;我和我的同事们&…...

开源自托管看板工具:基于Preact+Hono+SQLite的零云依赖方案

1. 项目概述&#xff1a;一个为自托管与AI协作而生的看板应用如果你正在寻找一个可以完全掌控在自己手里、没有订阅费用、又能无缝集成到你自己产品中的看板工具&#xff0c;那么clawnify/open-kanban这个项目值得你花时间深入研究。它不是一个玩具&#xff0c;而是一个生产就绪…...

ARM CoreSight DAP-Lite调试架构与双协议切换技术

1. ARM CoreSight DAP-Lite技术架构解析作为ARM调试体系的核心组件&#xff0c;DAP-Lite&#xff08;Debug Access Port Lite&#xff09;是嵌入式系统开发中连接调试工具与片上资源的桥梁。我在实际芯片调试中发现&#xff0c;这个仅约2mm面积的IP模块&#xff0c;却能实现传统…...

大数据量存储终极指南:10个高效数据分片技巧

大数据量存储终极指南&#xff1a;10个高效数据分片技巧 【免费下载链接】til :memo: Today I Learned 项目地址: https://gitcode.com/gh_mirrors/ti/til 在当今数据爆炸的时代&#xff0c;高效处理和存储海量数据已成为企业技术架构的核心挑战。数据分片作为一种关键的…...

Windows 10/11下MySQL 8.0.28安装失败?‘服务没有响应控制功能’报错保姆级修复指南

Windows平台MySQL安装报错终极解决方案&#xff1a;从"服务无响应"到完美运行 遇到MySQL安装过程中弹出"服务没有响应控制功能"的红色报错窗口时&#xff0c;很多开发者第一反应是重装系统或更换数据库——别急&#xff01;这个看似复杂的错误其实90%以上源…...

大模型风口已至:月薪30K+的AI Agent开发岗,你准备好了吗?

文章介绍了如何借助不同版本的Agents实现智能自动化&#xff0c;并详细描述了AI应用工程师和大模型算法工程师的岗位职责和任职要求。文章还强调了AI学习的重要性&#xff0c;指出最先掌握AI的人将具有竞争优势&#xff0c;并提供了大模型AI学习和面试资料&#xff0c;帮助读者…...

5大核心功能:让旧iOS设备重获新生的终极工具指南

5大核心功能&#xff1a;让旧iOS设备重获新生的终极工具指南 【免费下载链接】Legacy-iOS-Kit An all-in-one tool to restore/downgrade, save SHSH blobs, jailbreak legacy iOS devices, and more 项目地址: https://gitcode.com/gh_mirrors/le/Legacy-iOS-Kit 你是否…...

基于MCP协议的AI自动化Solana代币发行与资产管理实战

1. 项目概述&#xff1a;当AI助手成为你的Solana发币合伙人 如果你在Solana生态里折腾过&#xff0c;肯定知道发一个币有多麻烦。从构思名字、设计代币经济学、写合约、到部署、创建流动性池、再到上DEX工具&#xff08;比如Dexscreener&#xff09;做推广&#xff0c;每一步都…...