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

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} Si1 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[i1]+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 题意&#xff1a; 定义一个集合S为T的孩子是&#xff0c;对于S中的每一个元素x&#xff0c;在T中都能找到x1。 给定n&#xff0c;k&#xff0c;每一个集合中的元素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脚手架项目启动&#xff1b;使用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类的常用接口说明 &#xff08;只讲解最常用的接口&#xff09;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世界中&#xff0c;Express是一个广泛使用的、强大的Web应用程序框架。它为开发者提供了一系列的工具和选项&#xff0c;使得创建高效且可扩展的Web应用程序变得轻而易举。然而&#xff0c;对于初学者来说&#xff0c;配置和初始化Express应用程序可能会有些困难。为了…...

SpringMVC的工作流程及入门

目录 一、概述 ( 1 ) 是什么 ( 2 ) 作用 二、工作流程 ( 1 ) 流程 ( 2 ) 步骤 三、入门实例 ( 1 ) 入门实例 ( 2 ) 静态资源处理 给我们带来的收获 一、概述 ( 1 ) 是什么 SpringMVC是一个基于Java的Web应用开发框架&#xff0c;它是Spring Framework的一部…...

logging.level的含义及设置 【java 日志 (logback、log4j)】

日志级别 trace<debug<info<warn<error<fatal 常用的有&#xff1a;debug&#xff0c;info&#xff0c;warn&#xff0c;error 通常我们想设置日志级别&#xff0c;会用到 logging.level.rootinfo logging.level设置日志级别&#xff0c;后面跟生效的区域。r…...

第 3 章 栈和队列(链栈)

1. 背景说明 链栈是指用单链表实现的栈&#xff0c;其存储结构为链式存储&#xff0c;实现类似于队列的链式实现&#xff0c;不过在插入元素时链栈在头部插入&#xff0c;而 链式队列在尾部插入&#xff0c;本示例中实现为带头结点的链栈&#xff0c;即栈顶元素为栈指针的下一…...

嵌入式面试-经典问题

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拉流播放&#xff1a; ZLMediaKit在Windows上实现Rtmp流媒体服务器以及模拟rtmp推流和http-flv拉流播放_zlm流媒体服务器_霸道流氓气质的博客-CSDN博客 按照以上教程启动MediaServer.exe时提示&am…...

项目(智慧教室)第二部分,人机交互页面实现,

使用软件&#xff1a; 1.BmCvtST.exe 这是stm32Cubemx工程下的带三方软件。存在STemWin中。 作用&#xff1a; 图片变成.c文件格式。 2.CodeBlock 3.模拟器工程&#xff08;具体请看上一节&#xff09; 一。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 有什么区别&#xff1f;看到了吗&#xff1f; 3、看看docker启动后的镜像仓库都有什…...

ubuntu18.04.6的安装教程

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

小白的第一个RNN(情感分析模型)

平台&#xff1a;window10&#xff0c;python3.11.4&#xff0c;pycharm 框架&#xff1a;keras 编写日期&#xff1a;20230903 数据集&#xff1a;英语&#xff0c;自编&#xff0c;训练集和测试集分别有4个样本&#xff0c;标签有积极和消极两种 环境搭建 新建文件夹&am…...

华为云 存在部支持迁移的外键解决方法

DRS 检测出源端存在不支持的外键引用操作 MySQL、GaussDB(for MySQL)为源的全量增量或增量迁移、同步场景&#xff0c;以及MySQL、GaussDB(for MySQL)为源灾备场景 表1 源端存在不支持的外键引用操作 预检查项 源端存在不支持的外键引用操作。 描述 同步对象中存在包含CASC…...

C# winform控件和对象双向数据绑定

实现目的&#xff1a; 控件和对象双向数据绑定 实现结果&#xff1a; 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、零样本分类&#xff1a;在没有样本标签的情况下对文本进行分类。 2、nli:(Natural Language Inference),自然语言推理 3、xnli:(Cross-Lingual Natural Language Inference) ,是一种数据集&#xff0c;支持15种语言&#xff0c;数据集包含10个领域&#xff0c;每个领…...

代码随想录二刷day07

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣454. 四数相加 II二、力扣383. 赎金信三、力扣15. 三数之和四、力扣18. 四数之和 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

vscode(仍待补充)

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

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; 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安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

jdbc查询mysql数据库时,出现id顺序错误的情况

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