当前位置: 首页 > 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…...

ios xcode15 navigationController?.navigationBar.isHidden = false无效

xcode 15 用 navigationController?.setNavigationBarHidden(true, animated: false)隐藏navigationBar后&#xff0c;再调用 navigationController?.navigationBar.isHidden false无效 解决 用 navigationController?.navigationBar.isHidden true隐藏navigationBar...

Python二级 每周练习题20

练习一: 日期计算器 设计一款日期计算程序&#xff0c;能否实现下面的功能&#xff1a; (1)要求用户分别输入年、月、日&#xff08;分三次输入&#xff09;&#xff1b; (2)程序自动会根据输入的年月日计算出这一天是这一年的第几天&#xff1b; (3)输出格式为&#xff1a;这…...

深度学习-一个简单的深度学习推导

文章目录 前言1.sigmod函数2.sigmoid求导3.损失函数loss4.神经网络1.神经网络结构2.公式表示-正向传播3.梯度计算1.Loss 函数2.梯度1.反向传播第2-3层2.反向传播第1-2层 3.python代码4.MNIST 数据集 前言 本章主要推导一个简单的两层神经网络。 其中公式入口【入口】 1.sigmod…...

ES写入数据报错:retrying failed action with response code: 429

报错&#xff1a; 使用logstash导入分片数量为9的index发生错误,[logstash.outputs.elasticsearch] retrying failed action with response code: 429 ({"type">"es_rejected_execution_exception", "reason">"rejected execution …...

Redis给Lua脚本的调用

Redis给Lua脚本的调用 Redis为Lua提供了一组内置函数&#xff0c;这些函数可用于执行与Redis数据存储和操作相关的任务。这些内置函数可以在Lua脚本中使用&#xff0c;以便在Redis中执行各种操作。以下是一些常用的Redis Lua内置函数&#xff1a; 主要知道call就好了 redis.ca…...

Spring工具类--ReflectUtils的使用

原文网址&#xff1a;Spring工具类系列--ReflectUtils的使用_IT利刃出鞘的博客-CSDN博客 简介 本文介绍Spring的ReflectUtils的使用。 ReflectUtils工具类的作用&#xff1a;便利地进行反射操作。 Spring还有一个工具类&#xff1a;ReflectionUtils&#xff0c;它们在功能上…...

联盟 | 彩漩 X HelpLook,AI技术赋能企业效率提升

近日&#xff0c;AI 驱动的 PPT 协作分享平台「 彩漩 」与 AI 知识库搭建工具「 HelpLook」&#xff0c;携手为用户工作流注入更多智能和创造力&#xff0c;全面拥抱 AIGC 时代带来的机遇&#xff0c;致力于提供前沿的智能解决方案。 彩 漩 彩漩是一个以 AI 技术为基础、贯彻 …...

MATLAB m文件格式化

记录一个网上查到的目前感觉挺好用的格式化方法。 原链接&#xff1a; https://cloud.tencent.com/developer/article/2058259 压缩包&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1ZpQ9qGLY7sjcvxzjMPAitw?pwd6666 提取码&#xff1a;6666 下载压缩包&#xf…...

​分拆菜鸟将使阿里巴巴股票迎来新一轮上涨?

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 总结&#xff1a; &#xff08;1&#xff09;阿里巴巴(BABA)最近公布的季度财报显示&#xff0c;该公司有能力实现快速盈利。 &#xff08;2&#xff09;据报道&#xff0c;阿里巴巴正计划分拆菜鸟集团&#xff0c;并将在香…...

Excel 技巧记录-那些复杂的公式和函数

目标表格的关键字在行和列里&#xff0c;匹配源表格的行和列对应的关键字 **具体需求为&#xff1a;**表A叫Total_202308.xlsx&#xff0c;sheet叫摊销前分析&#xff0c;表B叫data.xlsx,sheet叫总部费用&#xff0c;表A的数据里&#xff0c;A列是科目名称&#xff0c;第9行是…...

网站建设没有图片/嘉兴百度seo

一、list转字符串命令&#xff1a;.join(list)其中&#xff0c;引号中是字符之间的分割符&#xff0c;如“,”&#xff0c;“;”&#xff0c;“\t”等等如&#xff1a;list [1, 2, 3, 4, 5].join(list) 结果即为&#xff1a;12345,.join(list) 结果即为&#xff1a;1,2,3,4,5二…...

上海网站建设与设计公司好/申请百度收录网址

一、问题引入 维护老项目&#xff0c;看到下面一个函数&#xff1a; /// <summary>/// 从ViewState中获取某个属性的值。如果该属性不存在&#xff0c;返回空字符串。/// </summary>/// <param name"PropertyName">属性名称</param>/// <…...

哪里有做兼职的网站/广告公司招聘

介绍 FAB&#xff0c;在Material Design中&#xff0c;一般用来处理界面中最常用&#xff0c;最基础的用户动作。它一般出现在屏幕内容的前面&#xff0c;通常是一个圆形&#xff0c;中间有一个图标。 FAB有三种类型&#xff1a;regular, mini, and extended。不要强行使用FAB…...

做网站同行/企业网站优化外包

编写完自己的程序&#xff0c;如何生成其对应的开发者文档以方便我们日后查看呢&#xff1f;使用 javadoc 开发工具即可生成一个开发者文档。本文将介绍使用 javadoc 如何生成开发者文档以及注意的问题。 1.文档注释 注释分为&#xff1a; 单行注释&#xff1a;// 注释内容多…...

如何自己做网站发布到服务器上面/河南靠谱seo电话

前边有一篇记录过不使用spring&#xff0c;直接在java代码中连接和操作mongodb数据库&#xff0c;这里就紧随其后记录一下使用spring的情况下&#xff0c;在java中简单操作mongodb。maven导包配置&#xff1a;因为涉及了sping以及springmvc&#xff0c;因此也需要导入它们相关的…...

阳狮做网站/小程序定制开发公司

ps命令 查看系统进程信息 如果要对进程进行监控和控制&#xff0c;首先必须了解当前进程的情况&#xff0c;基本也就是需要查看当前进程&#xff0c;ps命令是最同时也是非常强大的进程查看命令。使用该命令可以确定有哪些进程正在运行、进程运行的状态、进程是否结束、进程是否…...