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. 四数之和 前言 提示:这里可以添加本文要记录的大概内容࿱…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...