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

洛谷 P11626 题解

news 来源：原创 2025/5/15 2:50:41

$\color{blue}{\texttt{[Problem Discription]}}$

给定长度为 $n$ 的数组 $A_{1 \cdots n}$ ，求

$\sum\limits_{a=1}^{n}\sum\limits_{b=a+1}^{n}\sum\limits_{c=b+1}^{n}\sum\limits_{d=c+1}^{n}\sum\limits_{e=d+1}^{n}\sum\limits_{f=e+1}^{n}\sum\limits_{g=f+1}^{n}\left ( \gcd\limits_{i=1}^{a}A_{i}+\gcd \limits_{i=a+1}^{b} A_{i}+\gcd\limits_{i=b+1}^{c} A_{i} + \gcd \limits_{i=c+1}^{d} A_{i} +\gcd\limits_{i=d+1}^{e} A_{i} +\gcd\limits_{i=e+1}^{f} A_{i} +\gcd\limits_{i=f+1}^{g} A_{i} \right )$

对 $998244353$ 取模的结果。

其中 $\gcd\limits_{i=l}^{r} x_{i}$ 表示 $x_{l},x_{l+1},\dots,x_{r}$ 的最大公约数。

$\leq n \leq 1 \times 10^{5}, 1\leq x_{i} \leq 1 \times 10^{9}$ 。

$\color{blue}{\texttt{[Analysis]}}$

首先，对数据结构比较熟悉的同学应该知道，静态数组求区间最大公约数可以用 ST 表来解决。

事实上，ST 表的本质就是倍增算法。因此，只要是静态数组的问题，基本都可以用 ST 表解决。

只不过，对于求区间和、区间异或和之类的问题，每个数出现次数对最终答案是有影响的，因此 ST 表查询答案的时候也必须用 $O(\log n)$ 的算法（一步一步跳着查询）。而区间最大最小值、区间最大公约数这些问题和每个数出现次数没有关系，可以直接 $O (1)$ 查询。

式子很复杂，也无法用一般的数论方法化简。因此，只能考虑 dp。

设 $\gcd\limits_{i=1}^{a} A_{i}$ 为第一段和， $\gcd\limits_{i=a+1}^{b} A_{i}$ 为第二段和，以此类推。

记 $f_{k,i}$ 表示只考虑到第 $i$ 个数，求其前 $k$ 段和，且第 $i$ 个数必须划到第 $k$ 段和时所有方案的总和。 $g_{k,i}$ 表示只考虑到第 $i$ 个数，求其前 $k$ 段和，且第 $i$ 个数必须划到第 $k$ 段和时可行的区间划分的方案数。

最终答案即为：

$\sum\limits_{i=7}^{n}f_{7,i}$

则 $f$ 的转移方程为：

$f_{k,i}=\sum\limits_{j=1}^{i-1}\left ( f_{k-1,j} + g_{k-1,j} \times \gcd\limits_{x=j+1}^{i} A_{x} \right )$

$g$ 的转移方程为：

$g_{k,i}=\sum\limits_{j=1}^{i-1}g_{k-1,j}$

直接这么转移肯定会超时，考虑优化。显然 $g$ 可以用前缀和优化。

展开 $f$ 的转移方程：

$f_{k,i} = \color{red}{\sum\limits_{j=1}^{i-1} f_{k-1,j}}+\color{blue}{\sum\limits_{j=1}^{i-1} g_{k-1,j} \times \gcd\limits_{x=j+1}^{i} A_{x}}$

显然，红色部分也可以用前缀和优化。考虑优化蓝色部分。

固定 $i$ ，则 $u_{j}=\gcd\limits_{x=j+1}^{i} A_{x}$ 是一个变下限区间求最大公约数。区间右端点为 $i$ 是固定的。因此， $u_{j}$ 必然是 $A_{i}$ 的约数，且 $u_{j}$ 必然是 $u_{j+1}$ 的约数。故 $u_{j} \leq u_{j+1}$ 。

因此 $u$ 具有单调性，而 $A_{i}$ 的约数最多为 $log A_{i}$ 个，因此 $u$ 至多可以分为 $log A_{i}$ 段，每段内 $u$ 值相同。可以用二分法求出区间分界点。

对于 $u$ 值相同的区间，即 $\gcd\limits_{x=j+1}^{i} A_{x}$ 相同的区间， $g_{k-1,j}$ 的和可以用前缀和求出。

总的时间复杂度 $O(n \log^{2} n)$ 。

$\color{blue}{\text{Code}}$

const int N=1e5+100;
const int mod=998244353;struct ST_gcd{int f[22][N],n,_Log[N];void init(int n,int *a){(this->n)=n;_Log[0]=-1;for(int i=1;i<=n;i++){f[0][i]=a[i];_Log[i]=_Log[i>>1]+1;}for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[j][i]=gcd(f[j-1][i],f[j-1][i+(1<<(j-1))]);}int query(int l,int r){int s=_Log[r-l+1];return gcd(f[s][l],f[s][r-(1<<s)+1]);}
}st;//ST 表求区间最大公约数的模版int f[10][N],g[10][N],pref[10][N],preg[10][N];
int n,a[N],ans;int Bineary_Search(int left,int right,int i,int val){int l=left,r=right,ans=-1;while (l<=r){int mid=(l+r)>>1;if (st.query(mid,i)==val){ans=mid;r=mid-1;}else l=mid+1;}return ans;
}struct node{int l,r,val;
};
vector<node> idx[N];void calc_g(){for(int k=2;k<=7;k++)for(int i=k;i<=n;i++){g[k][i]=preg[k-1][i-1];preg[k][i]=(preg[k][i-1]+g[k][i])%mod;}
}
void calc_f(){for(int k=2;k<=7;k++)for(int i=k;i<=n;i++){f[k][i]=pref[k-1][i-1];for(node cur:idx[i]){int l=cur.l,r=cur.r,v=cur.val;f[k][i]=(f[k][i]+1ll*v*(((preg[k-1][r-1]-preg[k-1][l-2])%mod+mod)%mod)%mod)%mod;}pref[k][i]=(pref[k][i-1]+f[k][i])%mod;}
}int main(){n=read();for(int i=1;i<=n;i++)a[i]=read();st.init(n,a);for(int i=1;i<=n;i++){for(int r=i,v=0;r>=2;){v=gcd(a[r],v);int l=Bineary_Search(2,r,i,v);idx[i].push_back((node){l,r,v});r=l-1;}}for(int i=1;i<=n;i++){f[1][i]=gcd(f[1][i-1],a[i]);pref[1][i]=(pref[1][i-1]+f[1][i])%mod;g[1][i]=1;preg[1][i]=i;}calc_g();calc_f();for(int i=7;i<=n;i++)ans=(ans+f[7][i])%mod;printf("%d",ans);return 0;
}

洛谷 P11626 题解

[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription] 给定长度为 n n n 的数组 A 1 ⋯ n A_{1 \cdots n} A1⋯n，求 ∑ a 1 n ∑ b a 1 n ∑ c b 1 n ∑ d c 1 n ∑ e d 1 n ∑ f e 1 n ∑ g f 1 n ( gcd …...

编程日记 2025/5/15 2:50:41

Android学习制作app（ESP8266-01S连接-简单制作）

一、理论部分理论见arduino学习-CSDN博客和Android Studio安装配置_android studio gradle 配置-CSDN博客以下直接上代码和效果视频，esp01S的收发硬件代码目前没有分享，但是可以通过另一个手机网络调试助手进行模拟。也可以直接根据我的代码进行改动…...

编程日记 2025/5/15 2:50:36

一文读懂 RAG：LLM 借助检索打开思路

一、引言在自然语言处理（NLP）领域，随着深度学习技术的飞速发展，大型语言模型（LLMs）展现出了强大的语言理解和生成能力。然而，LLMs也存在一些局限性，如容易产生幻觉、知识更新不及时…...

编程日记 2025/5/12 22:32:50

使用istio实现权重路由

istio概述 **概述：**Istio 是一个开源的服务网格（Service Mesh）解决方案，主要用于管理、保护和监控微服务架构中的服务通信。它为微服务提供了基础设施层的控制功能，不需要更改应用程序的代码，从而解决服…...

编程日记 2025/5/13 12:42:11

DeepSeek发布新模型，遭遇大规模攻击，梁文锋回应证实为假，吴恩达盛赞DeepSeek！AI Weekly 1.27-2.2

📢本周AI快讯 | 1分钟速览🚀 1️⃣ 🖼️Janus-Pro-7B：DeepSeek发布7B开源多模态模型，视觉理解&生成能力超越DALL-E 3！ 2️⃣ 🚨DeepSeek遭遇大规模攻击：DDoS暴力破解&#xff…...

编程日记 2025/5/10 16:14:06

20250202在Ubuntu22.04下使用Guvcview录像的时候降噪

20250202在Ubuntu22.04下使用Guvcview录像的时候降噪 2025/2/2 21:25 声卡：笔记本电脑的摄像头自带的【USB接口的】麦克风。没有外接3.5mm接口的耳机。缘起：在安装Ubuntu18.04/20.04系统的笔记本电脑中直接使用Guvcview录像的时候底噪很大！ …...

编程日记 2025/5/12 9:00:37

直方图：摄影中的视觉数据指南

目录一、直方图基础：揭开它的神秘面纱二、解读直方图类型：亮度与色彩的密码 （一）亮度直方图 （二）RGB 直方图三、拍摄中巧用直方图：优化曝光与效果 （一）精准判断曝…...

编程日记 2025/5/13 10:08:03

OpenGL学习笔记（七）：Camera 摄像机（视图变换、LookAt矩阵、Camera类的实现）

文章目录摄像机/观察空间/视图变换LookAt矩阵移动相机（处理键盘输入）移动速度欧拉角移动视角（处理鼠标输入）缩放场景（处理滚轮输入）Camera类摄像机/观察空间/视图变换在上一节变换中，我们讨…...

编程日记 2025/5/12 10:30:47

冲刺一区！挑战7天完成一篇趋势性分析GBD DAY1-7

Day1. 公开数据库的挖掘太火热了,其中GBD数据库的挖掘又十分的火爆.那我就来挑战一篇GBD、一篇关于趋势性分析的GBD！ GBD数据库挖掘是目前的四大刊常客，经常出现在顶级期刊上面。这个数据库亮点就是：可视化，统计学简单、而数据可…...

编程日记 2025/5/13 10:56:02

解锁数据结构密码：层次树与自引用树的设计艺术与API实践

1. 引言：为什么选择层次树和自引用树？ 数据结构是编程中的基石之一，尤其是在处理复杂关系和层次化数据时，树形结构常常是最佳选择。层次树（Hierarchical Tree）和自引用树（Self-referencing Tree…...

编程日记 2025/5/10 16:13:46

【AudioClassificationModelZoo-Pytorch】基于Pytorch的声音事件检测分类系统

源码：https://github.com/Shybert-AI/AudioClassificationModelZoo-Pytorch 模型测试表模型网络结构batch_sizeFLOPs(G)Params(M)特征提取方式数据集类别数量模型验证集性能EcapaTdnn1280.486.1melUrbanSound8K10accuracy0.974, precision0.972 recall0.967, F1-s…...

编程日记 2025/5/12 11:58:43

ARM嵌入式学习--第十二天（WDOG，RTC）

--WDOG -介绍 WatchDog是为了能够防止程序跑飞而使用的一种硬件模块，如果你的程序没有跑飞，那么你的程序会定时的去喂看门狗；如果你的程序跑飞了，那么就不会再去喂狗了，如果超过了喂狗时间，那么狗就会自己…...

编程日记 2025/5/13 9:24:24

自动化构建-make/Makefile 【Linux基础开发工具】

文章目录一、背景二、Makefile编译过程三、变量四、变量赋值1、""是最普通的等号2、“:” 表示直接赋值3、“?” 表示如果该变量没有被赋值，4、""和写代码是一样的， 五、预定义变量六、函数**通配符** 七、伪目标 .PHONY八、其他常…...

编程日记 2025/5/10 0:18:57

三天急速通关JavaWeb基础知识：Day 2 前端基础知识（计划有变，前端工程化部分暂时搁置）

三天急速通关JavaWeb基础知识：Day 2 前端基础知识 0 文章说明1 HTML1.1 介绍1.2 基本结构及语法1.3 常见标签2 CSS2.1 介绍2.2 引入方式2.3 选择器2.4 浮动定位盒子模型 3 JavaScript3.1 介绍3.2 组成3.3 基础语法 4 Ajax4.1 介绍4.2 示例未完待续，前…...

编程日记 2025/5/12 23:14:15

Chapter2 Amplifiers, Source followers Cascodes

Chapter2 Amplifiers, Source followers & Cascodes MOS单管根据输入输出, 可分为CS放大器, source follower和cascode 三种结构. Single-transistor amplifiers 这一章学习模拟电路基本单元-单管放大器单管运放由Common-Source加上DC电流源组成. Avgm*Rds, gm和rds和…...

编程日记 2025/5/13 15:44:51

14-9-3C++STL的set容器

set容器的pair对组——set容器set.equal range(elem) 1.返回容器中与elem相等的上下限的两个迭代器；上限是闭区间，下限是开区间，如[beg, end) 2.函数返回两个迭代器，而这两个迭代器被封装在pair中 pair< set<int>::ite…...

编程日记 2025/5/12 5:10:01

用Impala对存储在HDFS中的大规模数据集进行快速、实时的交互式SQL查询的具体步骤和关键代码

AWS EMR（Elastic MapReduce）中应用Impala的典型案例，主要体现在大型企业和数据密集型组织如何利用Impala对存储在Hadoop分布式文件系统（HDFS）中的大规模数据集进行快速、实时的交互式SQL查询。以下是一个具体的案例说明…...

编程日记 2025/5/15 3:12:17

如何确认Linux嵌入式系统的触摸屏对应的是哪个设备文件(/dev/input/event1)？如何查看系统中所有的输入设备？输入设备的设备文件有什么特点？

Linux嵌入式系统的输入设备的设备文件有什么特点？ 在 Linux 中，所有的输入设备（如键盘、鼠标、触摸屏等）都会被内核识别为输入事件设备，并在 /dev/input/ 目录下创建相应的设备文件，通常是： …...

编程日记 2025/5/14 8:02:03

C++泛型编程指南08 auto decltype

文章目录 [TOC]第3章：auto占位符（C11～C17）3.1 auto关键字的重新定义3.2 类型推导规则 3.3 何时使用auto3.4 返回类型推导3.5 在Lambda表达式中使用auto3.6 非类型模板参数占位符总结第4章 decltype说明符（C11&#xf…...

编程日记 2025/5/13 14:30:44

php的使用及 phpstorm环境部署

php语法环境搭建：在小皮中新建网站，注意先填写域名再点击选择根目录。成功创建网站后，打开发现forbidden，因为新建的网站里是空的，需要新建index.php文件----> 在Phpstorm中左上角打开文件，打开那个文…...

编程日记 2025/5/15 0:52:58

人工智能学习（五）之机器学习逻辑回归算法

深入剖析机器学习逻辑回归算法一、引言在机器学习领域，逻辑回归是一种极为经典且应用广泛的算法。虽说名字里带有 “回归”，但它主要用于解决分类问题，在医学、金融、互联网等多个领域都发挥着关键作用。例如，在医学上辅助判断…...

编程日记 2025/5/14 13:24:29

Kubernetes学习之包管理工具（Helm）

一、基础知识 1.如果我们需要开发微服务架构的应用，组成应用的服务可能很多，使用原始的组织和管理方式就会非常臃肿和繁琐以及较难管理，此时我们需要一个更高层次的工具将这些配置组织起来。 2.helm架构： chart:一个应用的信息集合…...

编程日记 2025/5/15 8:21:31

数据结构课程设计（四）校园导航

4 校园导航 4.1 需求规格说明【问题描述】一个学校平面图，至少包括10个以上的场所，每个场所带有编号、坐标、名称、类别等信息，两个场所间可以有路径相通，路长（耗时）各有不同。要求读取该校园平面图&a…...

编程日记 2025/5/14 9:47:36

(done) MIT6.S081 2023 学习笔记 (Day7: LAB6 Multithreading)

网页：https://pdos.csail.mit.edu/6.S081/2023/labs/thread.html (任务1教会了你如何用 C 语言调用汇编，编译后链接即可) 任务1：Uthread: switching between threads (完成) 在这个练习中，你将设计一个用户级线程系统中的上下文切…...

编程日记 2025/5/13 17:43:45

大年初六，风很大

北京的风在立春附近的几天突然大了，正在盘算着这个冬天可能就这样平庸的去了，没成想风来了。走在风中，穿着本应该是三九天穿的冬装，紧闭着嘴，缩着身子，感受着这冬天该有的低温。这是冬天该有的样子&#xf…...

编程日记 2025/5/12 13:39:29

【算法】回溯算法专题③ ——排列型回溯 python

目录前置小试牛刀回归经典举一反三总结前置【算法】回溯算法专题① ——子集型回溯 python 【算法】回溯算法专题② ——组合型回溯剪枝 python 小试牛刀全排列 https://leetcode.cn/problems/permutations/description/ 给定一个不含重复数字的数组 nums ，返…...

编程日记 2025/5/13 9:41:22

利用deepseek参与软件测试基本架构如何又该在什么环节接入deepseek

利用DeepSeek参与软件测试，可以考虑以下基本架构和接入环节： ### 基本架构 - **数据层** - **测试数据存储**：用于存放各种测试数据，包括正常输入数据、边界值数据、异常数据等，这些数据可以作为DeepSeek的输入&…...

编程日记 2025/5/13 5:38:18

99.20 金融难点通俗解释：中药配方比喻马科维茨资产组合模型(MPT)

目录 0. 承前1. 核心知识点拆解2. 中药搭配比喻方案分析2.1 比喻的合理性 3. 通俗易懂的解释3.1 以中药房为例3.2 配方原理 4. 实际应用举例4.1 基础配方示例4.2 效果说明 5. 注意事项5.1 个性化配置5.2 定期调整 6. 总结7. 代码实现 0. 承前本文主旨： 本文通过中…...

编程日记 2025/5/12 16:45:38

为AI聊天工具添加一个知识系统之79 详细设计之20 正则表达式之7

本文要点要点 “正则表达式” 本来是计算机科学计算机科学的一个概念。本项目将它推广（扩张）到认知科学的“认知范畴”概念， 聚合（收敛）到神经科学的“神经元”概念。做法是：用reg 来系统化定义认知…...

编程日记 2025/5/13 9:41:16

[ Spring ] Spring Boot Mybatis++ 2025

文章目录 StructureMyBatis Controller AbilitiesConfigure Plugins and RepositoriesApply Plugins and Add DependenciesMyBatis Spring PropertiesMyBatis ApplicationMyBatis BeansMyBatis MapperMyBatis Query Builder Structure this blog introduce 3 ways using mybat…...

编程日记 2025/5/13 5:24:47

相关文章：