BZOJ 3160 万径人踪灭 解题报告

2023-11-10 21:41

本文主要是介绍BZOJ 3160 万径人踪灭 解题报告,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这个题感觉很神呀。将 FFT 和 Manacher 有机结合在了一起。

首先我们不管那个 “不能连续” 的条件,那么我们就可以求出有多少对字母关于某一条直线对称,然后记 $T_i$ 为关于直线 $i$ 对称的字母对的数量,那么答案(暂记为 $Ans$)就会是:

$$Ans = \sum 2^{T_i}-1$$

在不管那个 “不能连续” 的条件的时候,这个应该是显然的。

怎么算的话,我们弄两次。分别把 $a$ 和 $b$ 当做 $1$,另一个当做 $0$,然后就可以得到一个多项式,将这个多项式平方一下就可以得到所有的 $T_i$ 了,具体用 FFT 实现。

那么我们来管一管这个条件。

我们就可以用 Manacher 求出每一条直线的最长回文半径,然后记 $R_i$ 为直线 $i$ 的最长回文半径,那么实际上的总答案就会是:

$$Ans - \sum R_i$$

然后就做完啦。令 $n$ 为字符串的长度:

时间复杂度 $O(n\log n)$,空间复杂度 $O(n)$。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 typedef long long LL;
  6 #define N 262144 + 5
  7 #define _Mod 1000000007
  8 #define Mod 998244353
  9 #define g 3
 10 
 11 int n, len, Inv_len, d, ans, e[2][N], Rev[N], A[N], T[N], R[N];
 12 char s[N];
 13 
 14 inline int Inc(int u, int v, int p)
 15 {
 16     return u + v - (u + v >= p ? p : 0);
 17 }
 18 
 19 inline int power(int u, int v, int p)
 20 {
 21     int res = 1;
 22     for (; v; v >>= 1)
 23     {
 24         if (v & 1) res = (LL) res * u % p;
 25         u = (LL) u * u % p;
 26     }
 27     return res;
 28 }
 29 
 30 inline void FFT_Prepare()
 31 {
 32     for (len = n << 1; len != (len & -len); len += (len & -len)) ;
 33     for (int i = len; i > 1; i >>= 1) d ++;
 34     int w = power(g, (Mod - 1) / len, Mod);
 35     int Inv_w = power(w, Mod - 2, Mod);
 36     Inv_len = power(len, Mod - 2, Mod);
 37     for (int i = 0; i < len; i ++)
 38     {
 39         e[0][i] = !i ? 1 : (LL) e[0][i - 1] * w % Mod;
 40         e[1][i] = !i ? 1 : (LL) e[1][i - 1] * Inv_w % Mod;
 41         for (int j = 0; j < d; j ++)
 42             if ((i >> j) & 1) Rev[i] += 1 << (d - j - 1);
 43     }
 44 }
 45 
 46 inline void FFT(int *p, int op)
 47 {
 48     for (int i = 0; i < len; i ++)
 49         if (Rev[i] > i) swap(p[Rev[i]], p[i]);
 50     for (int k = 1, s = 1; k < len; k <<= 1, s ++)
 51         for (int i = 0; i < len; i ++)
 52         {
 53             if (i & k) continue ;
 54             int t = (i & (k - 1)) << (d - s);
 55             int u = Inc(p[i], (LL) p[i + k] * e[op][t] % Mod, Mod);
 56             int v = Inc(p[i], (LL) (Mod - p[i + k]) * e[op][t] % Mod, Mod);
 57             p[i] = u, p[i + k] = v;
 58         }
 59 }
 60 
 61 inline void FFT_Work(char key)
 62 {
 63     memset(A, 0, sizeof(A));
 64     for (int i = 0; i < n; i ++)
 65         A[i] = (s[i] == key);
 66     FFT(A, 0);
 67     for (int i = 0; i < len; i ++)
 68         A[i] = (LL) A[i] * A[i] % Mod;
 69     FFT(A, 1);
 70     for (int i = 0; i < len; i ++)
 71         T[i] = Inc(T[i], (LL) A[i] * Inv_len % Mod, Mod);
 72 }
 73 
 74 inline void Manacher()
 75 {
 76     for (int i = (n << 1); i >= 0; i --)
 77         s[i] = i & 1 ? s[i >> 1] : 'c';
 78     int mx = -1, id;
 79     for (int i = 0; i <= (n << 1); i ++)    
 80     {
 81         if (mx > i)
 82             R[i] = min(R[id * 2 - i], mx - i);
 83         else R[i] = 1;
 84         for (; i + R[i] <= (n << 1) && i - R[i] >= 0 && s[i + R[i]] == s[i - R[i]]; R[i] ++) ;
 85         if (i + R[i] > mx)
 86             mx = i + R[i], id = i;
 87     }
 88 }
 89 
 90 int main()
 91 {
 92     scanf("%s", s);
 93     n = strlen(s);
 94     FFT_Prepare();
 95     for (char ch = 'a'; ch <= 'b'; ch ++)
 96         FFT_Work(ch);
 97     for (int i = 0; i < len; i ++)
 98     {
 99         T[i] = (T[i] + 1) >> 1;
100         ans = Inc(ans, power(2, T[i], _Mod) - 1, _Mod);
101     }
102     Manacher();
103     for (int i = 0; i <= (n << 1); i ++)
104         ans = Inc(ans, _Mod - R[i] / 2, _Mod);
105     printf("%d\n", ans);
106     
107     return 0;
108 }
3160_Gromah

 

转载于:https://www.cnblogs.com/gromah/p/4652376.html

这篇关于BZOJ 3160 万径人踪灭 解题报告的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/385427

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

【干货分享】基于SSM的体育场管理系统的开题报告(附源码下载地址)

中秋送好礼 中秋佳节将至,祝福大家中秋快乐,阖家幸福。本期免费分享毕业设计作品:《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心,体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而,传统的体育场管理方式存在诸多问题,如资源分配不均、预约流程繁琐、数据统计不准确等,严重影响了体育场的使用效率和用户体验。

[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路,实操解析,解题软件使用,解题方法教程

题目来源 NSSCTF | 在线CTF平台因为热爱,所以长远!NSSCTF平台秉承着开放、自由、共享的精神,欢迎每一个CTFer使用。https://www.nssctf.cn/problem   [SWPUCTF 2021 新生赛]gift_F12 这个题目简单打开后是一个网页  我们一般按F12或者是右键查看源代码。接着我们点击ctrl+f后快速查找,根据题目给的格式我们搜索c

【中国国际航空-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 1. 暴力破解密码,造成用户信息泄露 2. 短信盗刷的安全问题,影响业务及导致用户投诉 3. 带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞 所以大部分网站及App 都采取图形验证码或滑动验证码等交互解决方案, 但在机器学习能力提高的当下,连百度这样的大厂都遭受攻击导致点名批评, 图形验证及交互验证方式的安全性到底如

hdu1879(解题报告)

继续畅通工程                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

hdu2033(解题报告)

人见人爱A+B                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

HDU3791(解题报告)

二叉搜索树                      Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                          Total Subm