COMPFEST 15H「组合数学+容斥」
Problem - H - Codeforces
题意:
定义一个集合S为T的孩子是,对于S中的每一个元素x,在T中都能找到x+1。
给定n,k,每一个集合中的元素x必须满足 1 < = x < = k 1<=x<=k 1<=x<=k且 c n t [ x ] < = 1 cnt[x]<=1 cnt[x]<=1,若n个集合重排后对于 1 < i < = n 1<i<=n 1<i<=n都可以满足 S i − 1 S_{i-1} Si−1为 S i S_i Si的孩子,则该n个集合是一个合法序列,求所有合法序列的个数。
思路:
定义 f [ i ] f[i] f[i]为最后一个集合中若 i i i存在,只看 i i i的贡献(可以构成
合法的之前集合
的总个数)。
则 f [ 1 ] = 1 , f [ i ] = f [ i − 1 ] + 1 f[1]=1,f[i]=f[i-1]+1 f[1]=1,f[i]=f[i−1]+1,因为最后一个集合里,1只能是自己冒出来的不能是由前面变来的,之后每一个数都可以是自己冒出来的(贡献为1),也可以是将使集合中出现i-1
的那个位置上的数提前出现一位,导致原来的i-1变成现在的i。由于最后一个集合中出现每一个数都是独立的,所以可以用乘法原理算得每种情况,求出 p r e [ i ] pre[i] pre[i]表示至少有n-i个空集
的集合有多少情况。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define eb emplace_back
#define m_p make_pair
const int mod = 998244353;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const ll N = 2e5+50;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数
int fac[N],inv[N];ll qp(ll a,ll b){ll ans=1;a%=mod;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}void init(){fac[0]=fac[1]=inv[0]=inv[1]=1;for(int i=2;i<=N;++i){fac[i]=1ll*fac[i-1]*i%mod; //阶乘inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod; //逆元}for(int i=2;i<=N;++i){inv[i]=1ll*inv[i]*inv[i-1]%mod;}
}void work() {init();int n,k;cin>>n>>k;ll ans=0;for(int i=1;i<=min(n,k);++i){ll res=(fac[i+1]*qp(i+1,k-i)%mod-fac[i]*qp(i,k-i+1)%mod+mod)%mod;//至少有n-(i+1)个空集-至少有n-i个空集ans=(ans+res*fac[n]%mod*inv[n-i]%mod)%mod;//恰有n-i个空集的情况}ans++;cout<<ans<<'\n';
}signed main() {io;int t=1;//cin >> t;while (t--) {work();}return 0;
}
相关文章:
COMPFEST 15H「组合数学+容斥」
Problem - H - Codeforces 题意: 定义一个集合S为T的孩子是,对于S中的每一个元素x,在T中都能找到x1。 给定n,k,每一个集合中的元素x必须满足 1 < x < k 1<x<k 1<x<k且 c n t [ x ] < 1 cnt[x…...

react快速开始(三)-create-react-app脚手架项目启动;使用VScode调试react
文章目录 react快速开始(三)-create-react-app脚手架项目启动;使用VScode调试react一、create-react-app脚手架项目启动1. react-scripts2. 关于better-npm-runbetter-npm-run安装 二、使用VScode调试react1. 浏览器插件React Developer Tools2. 【重点】用 VSCode …...

【C++入门】string类常用方法(万字详解)
目录 1.STL简介1.1什么是STL1.2STL的版本1.3STL的六大组件1.4STL的缺陷 2.string类的使用2.1C语言中的字符串2.2标准库中的string类2.3string类的常用接口说明 (只讲解最常用的接口)2.3.1string类对象的常见构造2.3.2 string类对象的容量操作2.3.3string…...
大数据错误
question1 : Could not locate Hadoop executable: D:\hadoop-3.3.1\bin\winutils.exe - 【已解决】Could not locate executable E:\Hadoop\bin\winutils.exe in the Hadoop binaries._could not locate executable e:\hadoop-3.3.1\bin\wi_君问归期魏有期的博客-CSDN博客 q…...
【Node.js】Express-Generator:快速生成Express应用程序的利器
在Node.js世界中,Express是一个广泛使用的、强大的Web应用程序框架。它为开发者提供了一系列的工具和选项,使得创建高效且可扩展的Web应用程序变得轻而易举。然而,对于初学者来说,配置和初始化Express应用程序可能会有些困难。为了…...

SpringMVC的工作流程及入门
目录 一、概述 ( 1 ) 是什么 ( 2 ) 作用 二、工作流程 ( 1 ) 流程 ( 2 ) 步骤 三、入门实例 ( 1 ) 入门实例 ( 2 ) 静态资源处理 给我们带来的收获 一、概述 ( 1 ) 是什么 SpringMVC是一个基于Java的Web应用开发框架,它是Spring Framework的一部…...
logging.level的含义及设置 【java 日志 (logback、log4j)】
日志级别 trace<debug<info<warn<error<fatal 常用的有:debug,info,warn,error 通常我们想设置日志级别,会用到 logging.level.rootinfo logging.level设置日志级别,后面跟生效的区域。r…...

第 3 章 栈和队列(链栈)
1. 背景说明 链栈是指用单链表实现的栈,其存储结构为链式存储,实现类似于队列的链式实现,不过在插入元素时链栈在头部插入,而 链式队列在尾部插入,本示例中实现为带头结点的链栈,即栈顶元素为栈指针的下一…...
嵌入式面试-经典问题
1、c语言内存模型 2、C语言中的变量定义在什么地方 3、C语言代码如何运行的、关于栈的相关 4、指针函数与函数指针的区分 5、Static关键字的作用 6、const作用 7、进程与线程的区别 8、链表与数组的区别 9、#define宏定义与typedef的区别...

ZLMeidaKit在Windows上启动时:计算机中丢失MSVCR110.dll,以及rtmp推流后无法转换为flv视频流解决
场景 ZLMediaKit在Windows上实现Rtmp流媒体服务器以及模拟rtmp推流和http-flv拉流播放: ZLMediaKit在Windows上实现Rtmp流媒体服务器以及模拟rtmp推流和http-flv拉流播放_zlm流媒体服务器_霸道流氓气质的博客-CSDN博客 按照以上教程启动MediaServer.exe时提示&am…...

项目(智慧教室)第二部分,人机交互页面实现,
使用软件: 1.BmCvtST.exe 这是stm32Cubemx工程下的带三方软件。存在STemWin中。 作用: 图片变成.c文件格式。 2.CodeBlock 3.模拟器工程(具体请看上一节) 一。emWin环境的搭建 1.codeBlock下载 开源免费。 2.使用stm的C…...

【docker】docker的一些常用命令-------从小白到大神之路之学习运维第92天
目录 一、安装docker-ce 1、从阿里云下载docker-cer.epo源 2、下载部分依赖 3、安装docker 二、启用docker 1、启动docker和不启动查看docker version 2、启动服务查看docker version 有什么区别?看到了吗? 3、看看docker启动后的镜像仓库都有什…...

ubuntu18.04.6的安装教程
目录 一、下载并安装virtualbox virtualbox7.0.8版本的安装 二、Ubuntu的下载与安装 ubuntu18.04.6操作系统 下载 安装 一、下载并安装virtualbox VirtualBox是功能强大的x86和AMD64/Intel64虚拟化企业和家庭使用的产品。VirtualBox不仅是面向企业客户的功能极其丰富的高…...

小白的第一个RNN(情感分析模型)
平台:window10,python3.11.4,pycharm 框架:keras 编写日期:20230903 数据集:英语,自编,训练集和测试集分别有4个样本,标签有积极和消极两种 环境搭建 新建文件夹&am…...
华为云 存在部支持迁移的外键解决方法
DRS 检测出源端存在不支持的外键引用操作 MySQL、GaussDB(for MySQL)为源的全量增量或增量迁移、同步场景,以及MySQL、GaussDB(for MySQL)为源灾备场景 表1 源端存在不支持的外键引用操作 预检查项 源端存在不支持的外键引用操作。 描述 同步对象中存在包含CASC…...

C# winform控件和对象双向数据绑定
实现目的: 控件和对象双向数据绑定 实现结果: 1. 对象值 -> 控件值 2. 控件值 -> 对象值 using System; using System.Windows.Forms;namespace ControlDataBind {public partial class MainForm : Form{People people new People();public Mai…...

达梦8 在CentOS 系统下静默安装
确认系统参数 [rootlocalhost ~]# ulimit -a core file size (blocks, -c) unlimited data seg size (kbytes, -d) unlimited【1048576(即 1GB)以上或 unlimited】 scheduling priority (-e) 0 file size (blocks, -f) unlimite…...
flink k8s sink到kafka报错 Failed to get metadata for topics
可能出现的3种报错 -- 报错1 Failed to get metadata for topics [...]. org.apache.kafka.common.errors.TimeoutException: Call-- 报错2 Caused by: org.apache.kafka.common.errors.TimeoutException: Timed out waiting to send the call. Call: fetchMetadata Heartbe…...
利用大模型MoritzLaurer/mDeBERTa-v3-base-xnli-multilingual-nli-2mil7实现零样本分类
概念 1、零样本分类:在没有样本标签的情况下对文本进行分类。 2、nli:(Natural Language Inference),自然语言推理 3、xnli:(Cross-Lingual Natural Language Inference) ,是一种数据集,支持15种语言,数据集包含10个领域,每个领…...
代码随想录二刷day07
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣454. 四数相加 II二、力扣383. 赎金信三、力扣15. 三数之和四、力扣18. 四数之和 前言 提示:这里可以添加本文要记录的大概内容࿱…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...

解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...

sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...

Java数组Arrays操作全攻略
Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...

[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...