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

[迷宫寻路 Round 3] 七连击

转化题意:求将一段序列划分为8段,求所有方案的前七段的每一段gcd的和的和.

首先朴素的dp很容易想到,设\(dp(i,j)\)为将前\(i\)位划分为前\(j\)段的答案,\(g(i,j)\)为将前\(i\)位划分为前\(j\)段的方案数.

于是有

\[\begin{aligned} g_{i,j} &= \sum_{k = 1}^{i-1} g_{k,j-1} \\ f_{i,j} &= \sum_{k = 1}^{i-1} f_{k,j-1}+g_{k,j-1}\times gcd(k+1,i) \end{aligned} \]

注:\(gcd(i,j)\)在本文中为序列第\(i\)为到第\(j\)位的\(gcd\)

其中\(gcd\)部分可用ST表\(O(nlogn)\)预处理后,\(O(1)\)求出,\(g\)数组也很显然前缀和\(O(n^2)\)求出,接下来只需要考虑\(f\)的处理

拆开有:

\[\begin{aligned} f_{i,j} &=\sum_{k = 1}^{i-1} f_{k,j-1}+\sum_{k = 1}^{i-1} g_{k,j-1}\times gcd(k+1,i)\end{aligned} \]

左侧很显然可以前缀和\(O(n^2)\)求.

右侧若无\(gcd\)这一项,那也可以前缀和,那如何去掉\(gcd\)的影响呢?

考虑当\(i\)确定时,\(gcd(k+1,i)\)最多只有\(log\)种取值,因为每次变化至少会少一个质因子而不会增加质因子.故考虑二分变化点,这样其中的每一段区间中\(gcd\)是不变的,是一个常量,故\(f_{i,j}\)可以通过\(log\)次转移求出,总时间复杂度\(O(7nlogWlogn)\).

注:这种做法对于序列中值为0的情况是时间复杂度没有任何影响的,因为是区间\(gcd\)所以还是满足最多只有\(log\)种情况.(我写代码时还加了特判,特判还算错了)

code:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+15,mod = 998244353,SZ = 2.2e6+15;
int gcd(int a,int b){if(b==0) return a;return gcd(b,a%b);
}
int add(int a,int b){ return a+b < mod ? a+b : a+b-mod;}
int sub(int a,int b){ return a<b ? a+mod-b : a-b;}
int mul(int a,int b){ return 1ll*a*b%mod;}
char buf[SZ],*pp=buf-1;
int in(){while(*++pp<'-');int w = *pp&15;while(*++pp>'-') w = (w<<3)+(w<<1)+(*pp&15);return w;
}
int n,a[N],f[N][10],sum[N],g[N][10],st[N][25],lg[N];
int query(int l,int r){int s = lg[r-l+1];return gcd(st[l][s],st[r-(1<<s)+1][s]);
}
int find(int i,int x){int l = 1 , r = i , ret = 0;while(l<=r){int mid=(l+r)>>1;if(query(mid+1,x)==query(i+1,x)) r = mid-1 , ret = mid;else l = mid+1;}return ret;
}
int main(){fread(buf,1,SZ,stdin);n=in();for(int i = 2 ; i<=n ; i++) lg[i] = lg[i>>1]+1;for(int i = 1 ; i<=n ; i++) a[i]=in(),st[i][0]=a[i];for(int i = 1 ; i<=n ; i++) g[i][1]=1;for(int i = 2 ; i<=7 ; i++){for(int j = 1 ; j<=n ; j++){g[j][i]=add(g[j-1][i],g[j-1][i-1]);}}int logn = lg[n];for(int i = 1 ; i<=logn ; i++){for(int j = 1 ; j+(1<<i)-1<=n ; j++){st[j][i]=gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);}}for(int i = 1 ; i<=n ; i++) f[i][1] = query(1,i);for(int j = 2 ; j<=7 ; j++){for(int i = 1 ; i<=n ; i++) f[i][j] = add(f[i-1][j],f[i-1][j-1]) , sum[i]=add(sum[i-1],g[i][j-1]) ;for(int i = 1 ; i<=n ; i++){int k = i-1;while(k){int tmp = find(k,i);f[i][j] = add(f[i][j],mul(query(tmp+1,i),sub(sum[k],sum[tmp-1])));k = tmp-1;}}}int ans = 0;for(int i = 1 ; i<=n ; i++) ans = add(ans,f[i][7]);printf("%d",ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=26857

相关文章:

  • 《程序员修炼之道:从小工到专家》阅读笔记
  • [笔记]树论笔记+做题记录
  • 云服务器部署大数据组件
  • 规模化网站SSL证书终极方案
  • 详细介绍:录制mp4
  • 10月8日
  • 【OpenGL ES】光栅化插值原理和射线拾取原理
  • HTML 速查列表 - 教程
  • Exp1
  • 20_uv_wsl_installation
  • 学习问题日记-4
  • Codeforces Round 1042 (CF2131) 补题笔记(A-E)
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名AI编程助手框架需求探索
  • 表格数据自动机器学习技术解析
  • 10/8
  • 2025.10.8
  • 【QT】QString 与QString区别 - 教程
  • 连通分量tarjan学习笔记
  • [Python/地图] 基于Python绘制地图
  • 实验任务1——8
  • 一款专门为 WPF 打造的开源 Office 风格用户界面控件库
  • dockercontainerd代理设置脚本
  • 实用指南:vue3+elementplus表格表头加图标及文字提示
  • 2025国庆集训总结
  • tampermonkey油猴脚本, 动画疯评分显示增强脚本
  • 9.29课后整理 - GENGAR
  • 深入解析:【QT】`QTextCursor::insertText()`中插入彩色文本
  • Java方法专题 - 动手动脑问题与实验总结
  • 2025年中盘点
  • 学习问题日记-3