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

P5821 【LK R-03】密码串匹配

[题目通道](【L&K R-03】密码串匹配 - 洛谷)

一道神题。

如果没有修改操作,翻转A数组或B数组后就是裸的FFT了

  • 如果每次操作都暴力修改+FFT时间复杂度显然爆炸

  • 如果每次操作都不修改,记下修改序列,询问时加上修改序列的贡献,复杂度仍然爆炸

于是考虑把两种方法结合起来,对操作序列分块

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define M 1000005
#define mod 998244353
#define g 3
using namespace std;
int n,ll,m,len=1,L,power3[M],power_inv3[M],rev[M],H,cnt;
int X[M],Y[M],E[M];
long long A[M],B[M],C[M],tmp_A[M],tmp_B[M],len_inv,sum;
long long add(long long u,long long v){return (u+=v)>=mod?u-mod:u;}
long long inv(long long x){return x==1?1:(mod-mod/x)*inv(mod%x)%mod;}
long long power(long long x,long long y){long long ans=1,now=x;for (register long long i=y;i;i>>=1,now=now*now%mod)if (i&1) ans=ans*now%mod;return ans;
}
char get_char(){//快读(字母)char c=getchar();while (c<'a'||c>'z') c=getchar();return c-'a';
}
int read(){//快读(整数)char c=getchar();int ans=0;while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();return ans;
}
void Write(long long x){//快速输出if (x<10) putchar(x^48);else Write(x/10),putchar((x%10)^48);return;
}
void NTT(long long *A,int flag){//NTT板子for (register int i=0;i<len;i++)if (i<rev[i]) swap(A[i],A[rev[i]]);for (register int l=1;l<len;l<<=1){long long T=(flag==1?power3[l]:power_inv3[l]);for (register int i=0;i<len;i+=(l<<1)){long long t=1;for (register int j=0;j<l;j++,t=t*T%mod){long long u=A[i+j],v=A[i+j+l]*t%mod;A[i+j]=add(u,v),A[i+j+l]=add(u,mod-v);}}}return;
}
void mul(){//多项式乘法for (register int i=0;i<len;i++) tmp_B[i]=B[i];NTT(tmp_B,1);for (register int i=0;i<len;i++) C[i]=tmp_A[i]*tmp_B[i]%mod;NTT(C,-1);for (register int i=0;i<len;i++) C[i]=C[i]*len_inv%mod;return;
}
long long query(int x){//处理询问操作long long now=C[x+ll-1];x+=ll-1;for (register int i=1;i<=X[0];i++) now+=Y[i]*A[x-X[i]];//暴力加上修改块内修改操作贡献return sum+E[x]-(x>=ll?E[x-ll]:0)-now*2;
}
int main(){n=read(),ll=read(),m=read();H=(int)(pow(n*log2(n),0.5))*3;while (len<=n+ll) len<<=1,++L;for (register int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<L-1);for (register int i=0;i<n;i++) tmp_A[i]=A[i]=get_char(),E[i]=E[i-1]+A[i]*A[i];for (register int i=0;i<ll;i++) B[i]=get_char(),sum+=B[i]*B[i];for (register int i=0,j=ll-1;i<j;i++,j--) swap(B[i],B[j]);for (register int l=1;l<len;l<<=1) power3[l]=power(g,(mod-1)/(l<<1)),power_inv3[l]=power(inv(g),(mod-1)/(l<<1));len_inv=inv(len);NTT(tmp_A,1);mul();//对密码串T只需要做一次FFTfor (register int i=1,opt;i<=m;i++){opt=read();if (opt==1) Write(query(read()-1)),putchar('\n');else {X[++X[0]]=ll-read(),Y[++Y[0]]=get_char();sum-=B[X[X[0]]]*B[X[X[0]]];int tmp=B[X[X[0]]];B[X[X[0]]]=Y[Y[0]],Y[Y[0]]-=tmp;sum+=B[X[X[0]]]*B[X[X[0]]];}if (X[0]==H) mul(),X[0]=Y[0]=0;//块的末尾暴力做NTT}return 0;
}

相关文章:

P5821 【LK R-03】密码串匹配

[题目通道](【L&K R-03】密码串匹配 - 洛谷) 一道神题。 如果没有修改操作&#xff0c;翻转A数组或B数组后就是裸的FFT了 如果每次操作都暴力修改FFT时间复杂度显然爆炸 如果每次操作都不修改&#xff0c;记下修改序列&#xff0c;询问时加上修改序列的贡献&#xff0c;…...

httpx,一个网络请求的 Python 新宠儿

大家好&#xff01;我是爱摸鱼的小鸿&#xff0c;关注我&#xff0c;收看每期的编程干货。 一个简单的库&#xff0c;也许能够开启我们的智慧之门&#xff0c; 一个普通的方法&#xff0c;也许能在危急时刻挽救我们于水深火热&#xff0c; 一个新颖的思维方式&#xff0c;也许能…...

计算机网络408考研 2014

1 计算机网络408考研2014年真题解析_哔哩哔哩_bilibili 1 111 1 11 1...

JavaScript 资源大全中文版

目录 JavaScript资源大全中文版 包管理器加载器组件管理器打包工具测试框架QA工具MVC 框架和库基于 Node 的 CMS 框架模板引擎文章和帖子数据可视化 时间轴电子表格 编辑器文档工具 文件函数式编程响应式编程数据结构日期字符串数字存储颜色国际化和本地化控制流路由安全性日志…...

如何获取能直接在浏览器打开的播放地址?

背景&#xff1a;需要在浏览器上直接打开设备的画面&#xff0c;但又不想二次开发 本文介绍一种极简的取流方式&#xff0c;不需要掌握前端开发知识&#xff0c;按照本文档拼接就能得到设备的播放地址 一、准备工作 1.将设备接入到萤石账号下。萤石设备接入指南&#xff1a;h…...

如何用 LangChain 实现一个Zero Shot智能决策器(附源码)

写在前面 最近一直在研究Agent和Tool的使用&#xff0c;今天给大家带来一篇何枝大佬&#xff08;知乎何枝&#xff09;的文章《如何用LangChain实现一个Zero Shot智能决策器》&#xff0c;并附上源码。 知乎&#xff1a;https://zhuanlan.zhihu.com/p/627333499LangChain是当…...

读完这本书,我终于搞懂了Transformer、BERT和GPT!【附PDF】

前言 《Transformer、BERT和GPT: 包括ChatGPT和提示工程》 是一本深入浅出地介绍自然语言处理领域前沿技术的专著&#xff0c;全书一共379页PDF&#xff0c;是截止到目前比较系统介绍NLP和GPT融合领域的书籍。 全书共十章&#xff0c;内容丰富&#xff0c;结构清晰&#xff0c…...

仿RabbitMq简易消息队列基础篇(Muduo库的使用)

TOC Muduo库简介 Muduo由陈硕⼤佬开发&#xff0c;是⼀个基于⾮阻塞IO和事件驱动的C⾼并发TCP⽹络编程库。他是一款基于主从Reactor模型的网络库&#xff0c;其使用的线程模型是one loop per thread, 所谓 one loop per thread 指的是&#xff1a; 一个线程只能有一个事件循…...

.net SqlSugarHelper

NuGet安装&#xff1a; SqlSugarCore using SqlSugar; using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;namespace Namespace {public class SqlSugarHelper{public string _connectionString Custom…...

“AI能不能代替某某职业”,到底谁在破防?

前几天&#xff0c;公司在午间分享时谈到一个有趣的辩题&#xff1a;“AI能不能代替产品经理”&#xff0c;不仅双方辩手打了个你来我往&#xff0c;就连下面的吃瓜群众也进入红温状态。 “AI能不能代替xx”已经成为一个普遍的话题&#xff0c;在某乎上随手一刷就是不同的职业…...

智慧图书馆:构建高效视频智能管理方案,提升图书馆个性化服务

一、背景分析 随着信息技术的飞速发展&#xff0c;智慧图书馆作为现代公共文化服务的重要载体&#xff0c;正逐步从传统的纸质阅读空间向数字化、智能化方向转型。其中&#xff0c;视频智能管理方案作为智慧图书馆安全管理体系的重要组成部分&#xff0c;不仅能够有效提升图书…...

React快速开发框架

本框架主要用于快速搭建项目 使用的基本库&#xff1a;webpackreactreact-routertypescript ps&#xff1a;有不足之处请多多包涵&#xff0c;提出意见或者建议 目的&#xff1a; 前端开发大多数时间是基于市面上比较流行的成品框架开始进行开发&#xff0c;途中遇到的问题大…...

【前端】记录各种控制台警告/bug

一、Element Plus 1、控制台警告&#xff1a;“Runtime directive used on component with non-element root node. The directives will not function as intended.” 错误原因&#xff1a;在 Vue 组件上使用了运行时指令&#xff08;指那些在运行时动态绑定到 DOM 元素上的指…...

猫咪掉毛严重怎么办?铲屎官家庭必备清理工具——宠物空气净化器

“毛&#xff0c;毛&#xff0c;毛&#xff0c;还是毛&#xff01;”铲屎官们每天都离不开和猫毛斗智斗勇&#xff0c;家里的每个角落都成了“战场”&#xff0c;掉毛的严重程度超乎想象。有时也在后悔当初怎么不养只无毛猫&#xff0c;而是把毛孩子接了回来&#xff0c;世上没…...

顺序表的实现——数据结构

线性表 文章目录 线性表线性表的定义和基本操作线性表的定义线性表的基本操作 线性表的顺序表示顺序表的定义顺序表的实现——静态分配顺序表的实现——动态分配顺序表的特点 线性表的定义和基本操作 线性表的定义 线性表&#xff08;Linear List&#xff09;的定义 ​ 线性…...

【模块化】CommonJS,AMD规范,CMD规范,ES6模块化

1. CommonJS Node.js基于CommonJS规范应运而生 1.1 commonjs规范语法导出模块 module.exports { a, b }1.2 commonjs规范语法引入模块 const mod require(./导出模块name)2. AMD 规范 RequireJS 是AMD规范的实现。是js文件和模块的加载器。 在没有单页应用&#xff08;angu…...

3.js - 顶点着色器、片元着色器的联系

1、定义与功能 顶点着色器 顶点着色器&#xff0c;是图形渲染管线中的第一个可编程阶段&#xff0c;它的主要任务是&#xff0c;处理从CPU发送到GPU的顶点数据&#xff0c;包括&#xff1a;1、顶点位置的变换&#xff08;如&#xff1a;模型空间 -> 世界空间 -> 视图控件…...

kotlin简介

Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言&#xff0c;被称之为 Android 世界的Swift&#xff0c;由 JetBrains 设计开发并开源。 Kotlin 可以编译成Java字节码&#xff0c;也可以编译成 JavaScript&#xff0c;方便在没有 JVM 的设备上运行。 在Google I/O 2017…...

Mintegral出海系列:解锁全球应用商店新增长路径

在全球化竞争的浪潮中&#xff0c;面对打法各异的应用和游戏品类&#xff0c;以及全球数百个环境不同的国家和地区&#xff0c;开发者们正面临着前所未有的挑战。Mintegral「出海ing」系列专题内容&#xff0c;助力出海开发者选准赛道探索新的增长路径。 据近期数据显示&#x…...

Qt 哈希加密之 QCryptographicHash

【写在前面】 QCryptographicHash 是 Qt 框架中提供的一个类&#xff0c;它用于实现加密散列函数&#xff0c;也就是我们常说的哈希函数。哈希函数能够将任意长度的数据转换为固定长度的哈希值&#xff0c;这个哈希值通常用于数据的完整性校验、密码存储等场景。 什么是哈希函数…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...