2023年ICPC亚洲合肥赛区赛 C. Cyclic Substrings

题目

题解

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
const int maxn = 6e6 + 5;
const int mod = 998244353;
int fail[maxn];//fail[i]表示i结点代表的回文串的最大回文后缀的编号 
int len[maxn]; //len[i]表示结点i代表的回文串的长度 
int trie[maxn][26], tot = 1;//tot初始为1!!!! 
int cnt[maxn];//结点i代表的回文串出现了多少次
int ind[maxn];
string s;
int get(int x, int i){//x是以s[i-1]结尾的回文串,返回以s[i-1]结尾且s[i-len[x]-1]==s[i]的回文串的对应结点编号 
	while(i - len[x] - 1 < 0 || s[i - len[x] - 1] != s[i]) x = fail[x];
	return x;
}
signed main(){
	int i, j;
	int n;
	cin >> n;
	cin >> s;
	s = s + s;
	int cur = 0;
	int pos, last = 0;
	fail[0] = 1;
	fail[1] = 0;
	len[0] = 0;
	len[1] = -1;
	for(i = 0; i < 2 * n; i++){
		pos = get(cur, i);//cur是以s[i-1]结尾的最大回文串 
		int idx = s[i] - '0';
		if(!trie[pos][idx]){ 
			tot++; 
			int t = get(fail[pos], i);
			fail[tot] = trie[t][idx];
			ind[trie[t][idx]]++;
			trie[pos][idx] = tot;//把新建的结点接在pos下面 
			len[tot] = len[pos] + 2;
			// cnt[tot] = cnt[fail[tot]] + 1;
		}
		cur = trie[pos][idx];
		if(i > n - 1)//只计算以 后半串的字符 结尾的最长回文串,否则会重复
			cnt[cur]++;//结点cur代表的回文串出现了多少次
	}
	
	ll res = 0;
	queue<int> q;
	for(int i = 2; i <= tot; i++){
		// if(len[i] > n) continue;
		if(!ind[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		int v = fail[u];
		// if(len[v] > n) continue;
		cnt[v] += cnt[u];//一个回文串出现一次,那么它的回文后缀也出现一次
		if(--ind[v] == 0){
			q.push(v);
		}
	}
	for(int i = 2; i <= tot; i++){
		if(len[i] > n) continue;
		// cout << i << ' ' << len[i] << ' ' << cnt[i] << '\n';
		res = (res + 1LL * len[i] * cnt[i] % mod * cnt[i] % mod) % mod;
	}
	cout << res << '\n';
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

大模型涌现判定

什么是大模型&#xff1f; 大模型&#xff1a;是“规模足够大&#xff0c;训练足够充分&#xff0c;出现了涌现”的深度学习系统&#xff1b; 大模型技术的革命性&#xff1a;延申了人的器官的功能&#xff0c;带来了生产效率量级提升&#xff0c;展现了AGI的可行路径&#x…

UDP/TCP协议

网络层只负责将数据包送达至目标主机&#xff0c;并不负责将数据包上交给上层的哪一个应用程序&#xff0c;这是传输层需要干的事&#xff0c;传输层通过端口来区分不同的应用程序。传输层协议主要分为UDP&#xff08;用户数据报协议&#xff09;和TCP&#xff08;传输控制协议…

mongodb-7.0.14分片副本集超详细部署

mongodb介绍&#xff1a; 是最常用的nosql数据库&#xff0c;在数据库排名中已经上升到了前六。这篇文章介绍如何搭建高可用的mongodb&#xff08;分片副本&#xff09;集群。 环境准备 系统系统 BC 21.10 三台服务器&#xff1a;192.168.123.247/248/249 安装包&#xff1a…

Javaweb基础-vue

Vue.js Vue是一套用于构建用户界面的渐进式框架。 起步 引入vue <head><script src"static/js/vue2.6.12.min.js"></script> </head> 创建vue应用 <body> <div id"index"><p>{{message}}</p> </div>…

Java的walkFileTree方法用法【FileVisitor接口】

在Java旧版本中遍历文件系统只能通过File类通过递归来实现&#xff0c;但是这种方法不仅消耗资源大而且效率低。 NIO.2的Files工具类提供了两个静态工具方法walk()和walkFileTree()可用来高效并优雅地遍历文件系统。walkFileTree()功能更强&#xff0c;可自定义实现更多功能&am…

5.3章节python中字典:字典创建、元素访问、相关操作

1.字典的创建和删除 2.字典的访问和遍历 3.字典的相关操作 4.字典的生成式 一、字典的创建和删除 字典&#xff08;dictionary&#xff09;是一种用于存储键值对&#xff08;key-value pairs&#xff09;的数据结构。每个键&#xff08;key&#xff09;都映射到一个值&#xf…

基于FPGA的信号发生器verilog实现,可以输出方波,脉冲波,m序列以及正弦波,可调整输出信号频率

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 (完整程序运行后无水印) 输出方波 输出脉冲波 输出m随机序列 输出正弦波 2.算法运行软件版本 vivado2019.2 3.部分核心程序 &#xff08;完整…

顺序表算法题【不一样的解法!】

本章概述 算法题1算法题2算法题3彩蛋时刻&#xff01;&#xff01;&#xff01; 算法题1 力扣&#xff1a;移除元素 我们先来看这个题目的要求描述&#xff1a; 把与val相同数值的元素移除掉&#xff0c;忽略元素的相对位置变化&#xff0c;然后返回剩下与val值不同的元素个数…

OpenCV高级图形用户界面(10)创建一个新的窗口函数namedWindow()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 创建一个窗口。 函数 namedWindow 创建一个可以作为图像和跟踪条占位符的窗口。创建的窗口通过它们的名字来引用。 如果已经存在同名的窗口&am…

Docker搭建Cisco AnyConnect 教程

本章教程搭建一个Cisco AnyConnect 连接教程。 一、下载文件 因为是基于Docker方式进行搭建的,所以需要提前安装好Docker,本章不介绍如何安装Docker,可以自行百度解决。 通过网盘分享的文件:ocserv-docker 链接: https://pan.baidu.com/s/14-2p9jenqE0KWzMilVzV-A?pwd=4yd…

小O睡眠省电调研

摘要 AI 预测睡眠 断网 杀应用为主的策略 UI 睡眠识别 AI 识别 将亮灭屏、音频、上传下载、运动状态数据存到xml中&#xff0c;供预测分析 睡眠策略 OPPO 睡眠省电 1. sOSysNetControlManagerNewInstance&#xff1a;断网&#xff08;wifi\mobiledata&#xff09;2. S…

Windows系统部署redis自启动服务【亲测可用】

文章目录 引言I redis以本地服务运行(Windows service)使用MSI安装包配置文件,配置端口和密码II redis服务以终端命令启动缺点运行redis-server并指定端口和密码III 知识扩展确认redis-server可用性Installing the Service引言 服务器是Windows系统,所以使用Windows不是re…

【web】JDBC

项目连接数据库 右侧导航栏找到databsae 如果没有驱动&#xff0c;先下载驱动 填写数据库用户名密码 勾选对应的表即可 JDBC代码流程 1,配置信息 2,加载驱动 从MySQL Connector/J 5.1版本开始&#xff0c;推荐使用com.mysql.cj.jdbc.Driver这个新的驱动类。 3,链接数据库…

java集合(二)--set收尾+HashMap

文章目录 1.linkedhashset的介绍2.linkedhashset源码分析3.Map的基本介绍31.基本属性3.2map里面的集合以及内部数据类型 4.Map接口的常见方法5.map里面的遍历的方法5.1根据key直接遍历5.2直接拿到这个value值5.3使用这个entry遍历 6.hashmap扩容转化红黑树的模拟7.hashtable底层…

AJAX——POST 设置请求体参数

1、是在请求体 send 中来设置的 2、参数设置的形式可以以 url 设置参数的形式来设置 ① 用 &#xff1f;分隔 ② 添加参数的名字与参数值&#xff08;中间使用 &#xff09; ③ 有多个参数&#xff0c;各个参数之间用 & 分隔 3、实际上参数设置的内容可以是任意的&…

python爬虫加解密分析及实现

第一种&#xff1a; 1、找到加密的接口地址&#xff0c;通过加密的接口地址全局搜索 2、通过打断点的方式&#xff0c;操作页面&#xff0c;跑到断点处时&#xff0c;即可找到加密串&#xff0c;如图二&#xff1b; 3、找到用的是哪种加密方式&#xff0c;如&#xff1a; cr…

freertos的任务管理

任务函数 任务被实现为C函数。它们唯一特别的地方是它们的原型&#xff0c;它必须返回void并接受void指针参数。以下是函数原型。 void ATaskFunction( void *pvParameters );每个任务本身都是一个小程序。它有一个入口点&#xff0c;通常会在无限循环中永远运行&#xff0c;…

力扣 中等 143.重排链表

文章目录 题目介绍题解 题目介绍 题解 class Solution {public void reorderList(ListNode head) {ListNode mid middleNode(head);ListNode head2 reverseList(mid);while (head2.next ! null) {ListNode nxt head.next;ListNode nxt2 head2.next;head.next head2;head2.…

一次恶意程序分析

首先F12shift查看字符表 字符表发现可疑字符串 双击进入 再tab 进入这里 推测为main函数 可见一些可疑的api FindResourceW推测该木马使用了资源加载 VirtualAlloc申请内存 然后sub_1400796E0 有 dwSize 参数 推测为 拷贝内存 memcpy类似函数 、 然后sub_140078CB0函数 跟进函…

题目 3161: 蓝桥杯2023年第十四届省赛真题-子矩阵

题目 代码 #include <bits/stdc.h> using namespace std; typedef long long ll; const int N 1010, mod 998244353; int g[N][N]; int rmin[N][N], rmax[N][N]; ll mmin[N][N], mmax[N][N]; int q[N * N]; int hh, tt; int n, m, a, b; int main() {cin >> n &…