ARC140D One to One
ARC140D One to One
题目大意
对于一个长度为nnn的整数序列X=(x1,x2,…xn)X=(x_1,x_2,\dots x_n)X=(x1,x2,…xn),每个元素都在111到nnn之间,令f(X)f(X)f(X)表示以下问题的答案:
- 有一个nnn个顶点nnn条边的无向图(可能有重边和自环),第iii条边连接iii和XiX_iXi,求联通块的数量
给一个正整数nnn和一个长度为nnn的序列A=(a1,a2…an)A=(a_1,a_2\dots a_n)A=(a1,a2…an),其每一个元素都在111到nnn之间,或者为−1-1−1。
你可以将每个值为−1-1−1的aia_iai变为任意一个111到nnn之间的数,求所有情况下f(A)f(A)f(A)的和。输出答案对998244353998244353998244353取模。
题解
令kkk表示ai=−1a_i=-1ai=−1的元素的个数。
我们可以先将ai≠−1a_i\neq -1ai=−1的边连上,那么现在图上的每一个连通块都是树或环或基环树。
如果是树的话,则这个连通块有且只有一个ai=−1a_i=-1ai=−1的点
如果是环或基环树的话,则这个连通块没有ai=−1a_i=-1ai=−1的点
我们可以先把环和基环树的贡献算出来,每个环或基环树的贡献为nkn^knk,因为不管怎么连,环或基环树都会有111的贡献。那么如果有树向环或基环树连边,则这棵树不计算贡献。
树与环或基环树连边的贡献不需计算,那么我们只需要求树与树连边的贡献了。
因为每棵树只有一条边连出去,所以我们可以将每棵树看成一个点。
如果不连向环和基环树,那么这些树一定会形成一个环。对于一个顺序已确定的环,形成这样的环的方案数为∏sizi\prod siz_i∏sizi。
我们考虑DP。设fif_ifi表示形成长度为iii的环的方案数,那么对于每个点jjj,有转移式
fi=fi+fi−1×sizkf_i=f_i+f_{i-1}\times siz_kfi=fi+fi−1×sizk
求出fff后我们考虑如何计算答案。对于所有长度为iii的环的贡献为fi×(i−1)!×nk−if_i\times (i-1)!\times n^{k-i}fi×(i−1)!×nk−i。其中(i−1)!(i-1)!(i−1)!表示iii个点按不同顺序可以构成(i−1)!(i-1)!(i−1)!个不同的环,nk−in^{k-i}nk−i表示其他n−kn-kn−k个点可以任意连边。
这样问题就解决了,时间复杂度为O(n2)O(n^2)O(n2)。
code
#include<bits/stdc++.h>
using namespace std;
int n,tot=0,vt=0,a[2005],d[5005],l[5005],r[5005],s[2005],z[2005],siz[2005];
long long ans,f[2005],jc[2005],mi[2005];
long long mod=998244353;
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u){z[u]=1;siz[u]=1;for(int i=r[u];i;i=l[i]){if(!z[d[i]]){dfs(d[i]);siz[u]+=siz[d[i]];}}
}
int main()
{scanf("%d",&n);jc[0]=mi[0]=1;for(int i=1;i<=n;i++){jc[i]=jc[i-1]*i%mod;mi[i]=mi[i-1]*n%mod;}for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==-1) continue;add(i,a[i]);add(a[i],i);}for(int i=1;i<=n;i++){if(a[i]==-1){dfs(i);s[++vt]=siz[i];}}for(int i=1;i<=n;i++){if(!z[i]){dfs(i);ans=(ans+mi[vt])%mod; }}f[0]=1;for(int i=1;i<=vt;i++){for(int j=i;j>=1;j--) f[j]=(f[j]+f[j-1]*s[i]%mod)%mod;}for(int i=1;i<=vt;i++){ans=(ans+f[i]*jc[i-1]%mod*mi[vt-i]%mod)%mod;}printf("%lld",ans);return 0;
}
相关文章:
ARC140D One to One
ARC140D One to One 题目大意 对于一个长度为nnn的整数序列X(x1,x2,…xn)X(x_1,x_2,\dots x_n)X(x1,x2,…xn),每个元素都在111到nnn之间,令f(X)f(X)f(X)表示以下问题的答案: 有一个nnn个顶点nnn条边的无向图(可能有重边和…...

联合身份验证与Cognito
Hello大家好,我们接下来讨论AWS联合身份验证的内容。 AWS联合身份验证 对于考试,联合身份验证部分是一块非常重要的内容。那什么是联合身份验证,它是做什么用的呢? 联合身份验证,是用来允许AWS外部用户,如…...

day18_常用API之String类丶Object类
String概述 java.lang.String 类代表字符串,String类定义的变量可以用于指向字符串对象,同时String类提供了很多操作字符串的功能,我们可以直接使用。Java 程序中的所有字符串文字(例如“abc”)都为此类的对象 特点:St…...
OSG三维渲染引擎编程学习之五十五:“第五章:OSG场景渲染” 之 “5.13 一维纹理”
目录 第五章 OSG场景渲染 5.13 一维纹理 5.13.1 一维纹理介绍 5.13.2 一维纹理示例 第五章 OSG场景渲染 OSG存在场景树和渲染树,“场景数”的构建在第三章“OSG场景组织”已详细阐明,本章开始...

RTOS随笔之FreeRTOS启动与同步方法
RTOS启动与同步机制RTOS启动任务切换场景任务同步机制队列信号量事件组任务通知任务延时RTOS启动 FreeRTOS在任务创建完成后调用函数vTaskStartScheduler()启动任务调度器。 vTaskStartScheduler()任务启动函数详解 void vTaskStartScheduler( void ) {BaseType_t xReturn;xR…...

【AI/NLP】InstructGPT数据标注问题
文章目录1 背景介绍2 标记员筛选2.1 标记员筛选标准3 数据集及其标注3.1 预训练3.2 微调3.2.1 SFT-demonstration data3.2.2 RM-comparison data3.3 数据集大小4 模型实现1 背景介绍 ChatGPT的训练过程与InstructGPT相近,大致分为三步: SFT:…...

三次握手和四次挥手
文章目录TCP三次握手为什么要三次握手三次握手可以携带数据吗?三次握手失败,服务端会如何处理?ISN代表什么,意义,何要动态随机什么是半连接队列第2次握手传回了ACK,为什么还要传回SYN?为什么要四次挥手TCP…...

Jmeter常用断言之响应断言详解
响应断言是最常用的一种断言方法,主要是对响应结果中的文本内容进行断言,比如响应结果是否包含指定的值,或者是否等于指定的值。响应断言可以适用各种返回类型的响应结果,如:Test、html、application/json、applicatio…...
【Python学习笔记】36.Python3 MySQL - mysql-connector 驱动(1)
前言 MySQL 是最流行的关系型数据库管理系统,本章节为大家介绍使用 mysql-connector 来连接使用 MySQL, mysql-connector 是 MySQL 官方提供的驱动器。 Python3 MySQL - mysql-connector 驱动 我们可以使用 pip 命令来安装 mysql-connector࿱…...

计算机SCI论文课题设计需要注意什么? - 易智编译EaseEditing
课题设计就要本着严谨性和可行性来进行。实验设计的类型要选择准确,统计学的方法要运用合理,研究对象和观察指标的选择也要符合研究目的的要求,技术路线要清晰明了。 关于课题的设计的可行性也要综合考虑,比如前期的相关工作基础…...

Quartz入门教程
本文参考文章编写 Quartz 官网 Quartz 是 OpenSymphony 开源组织在 Job Scheduling 领域又一个开源项目,是完全由 Java 开发的一个开源任务日程管理系统,“任务进度管理器”就是一个在预先确定(被纳入日程)的时间到达时ÿ…...
TypeScript 学习之 function
函数可以实现抽象层,模拟类,信息隐藏和模块。 函数有:有名字的函数、匿名函数 在 JavaScript 中的函数 // 有名字的函数 function add(x, y) {return x y; }// 匿名函数 let myAdd function (x, y) {return x y; };函数类型 typescript 可…...

【云计算自学路线】
云计算包含的技术内容和涉及的方向比较多,一定要进行系统化的学习才能更好的掌握这门技术。 云计算作为互联网新技术领域,现阶段也是出于高速发展期,想学习加入云计算行业的小伙伴可以抓紧机会了,跟着小课一起来了解云计算以及它…...
code01 v2黑屏、花屏、死机、断电重启、休眠死机的进来
症状解决 长话简说,症状如下: 使用浏览器、播放视频等,遇到突然死机或花屏死机的情况 关闭硬件加速,如:浏览器中设置关闭硬件加速,出现这种症状的软件都需要设置 开机电流音、播放与暂停时喇叭吱吱想、打…...

分享107个HTML电子商务模板,总有一款适合您
分享107个HTML电子商务模板,总有一款适合您 107个HTML电子商务模板下载链接:https://pan.baidu.com/s/1VW67Wjso1BRpH7O3IlbZwg?pwd0d4s 提取码:0d4s Python采集代码下载链接:采集代码.zip - 蓝奏云 Aplustemplates 购物模板…...

Barra模型因子的构建及应用系列三之Momentum因子
一、摘要 在之前的Barra模型系列文章中,我们已经初步讲解、构建了Size因子和Beta因子,并分别创建了对应的单因子策略。通过回测发现,其中Size因子的小市值效应具有很强的收益能力。而本篇文章将在该系列下进一步构建Momentum因子。 二、模型…...
8.2.1.3 索引合并优化
索引合并访问方法检索具有多个范围扫描的行,并将其结果合并为一个。此访问方法仅合并来自单个表的索引扫描,而不是跨多个表的扫描。合并可以生成其基础扫描的合并、交叉或交叉的合并。 可以使用索引合并的查询示例: SELECT * FROM tbl_name…...
水雨情在线小能手-雨量水位报警站
雨量水位报警站由水位探测器、雨量传感器、报警灯、扩音器、太阳能板和采集传输控制器组成。实时采集水位等级,三个水位探测器对应3个水位等级,当现场水面浸没相应探测器时,本机会实时发出语音报警,同时可发送相应的预警/报警等级…...

【蓝桥杯集训4】双指针专题(6 / 6)
目录 3768. 字符串删减 - 滑动窗口ac 799. 最长连续不重复子序列 - 滑动窗口 800. 数组元素的目标和 - 二分ac 2816. 判断子序列 - 双指针 1238. 日志统计 - 滑动窗口 1240. 完全二叉树的权值 - 双指针 1、前缀和 - 通过了 5/12个数据 2、双指针 3768. 字符串删减 -…...
文件流,gzip解压,压缩
目录 文件画布 写入 (空文件Foutnew File(Parent,entry.getName());)FileOutputStream outnew FileOutputStream(Fout);BufferedOutputStream Boutnew BufferedOutputStream(out);其他流量基于基础包装文件--文件流---字节流 顺序pbf一般是形成后再压缩目…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》
近日,嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》,海云安高敏捷信创白盒(SCAP)成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天,网络安全已成为企业生存与发展的核心基石,为了解…...

VSCode 使用CMake 构建 Qt 5 窗口程序
首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...
深入解析 ReentrantLock:原理、公平锁与非公平锁的较量
ReentrantLock 是 Java 中 java.util.concurrent.locks 包下的一个重要类,用于实现线程同步,支持可重入性,并且可以选择公平锁或非公平锁的实现方式。下面将详细介绍 ReentrantLock 的实现原理以及公平锁和非公平锁的区别。 ReentrantLock 实现原理 基本架构 ReentrantLo…...
【Java】Ajax 技术详解
文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...