首页 > 其他分享 >【题解】SP8836 SEQ7

【题解】SP8836 SEQ7

时间:2022-08-30 14:24:46浏览次数:83  
标签:10 le 题解 sum SP8836 Lemma maxn SEQ7 预处理

Link

Prologue

大大滴诈骗题/oh

Description

定义数列 \(\{g(n)\}_{n\in \mathbb N^*}\):\(g(1)=1\),\(g(n)\) 为 \(n\) 在数列中出现的次数。

给定 \(n\)(\(n\le 10^{13}\)),求 \(g(n)\)。

\(\{g(n)\}_{n\in\mathbb N^*}\) 其实就是 A001462 Golomb's Sequence。

Solution

观测 OEIS 可以得到两个性质:

Lemma 1: \(g(n+1)=1+g(n+1-g(g(n)))\).

Proof:把 \(g(n)\) 值相同的一段视作一“块”,则 \(g(g(n))\) 为 \(n\) 所在块的长度。由于相邻块的长度最多相差 \(1\)(因为 \(g(n)\) 与 \(g(n+1)\) 最多相差 \(1\)),\(n+1-g(g(n))\) 一定能跳到 \(n+1\) 的上一块。于是得证。

Lemma 2: 若 \(\sum_{i< n}g(i)<k\le\sum_{i\le n}g(i)\),则 \(g(k)=n\)。

Proof:考虑 \(n\) 第一次出现的位置,一定是 \(1\sim n-1\) 的数量 \(+1\),即 \(\left(\sum_{i<n}g(i)\right)+1\)。显然又有 \(n\) 最后一次出现的位置为 \(\sum_{i\le n}g(i)\)。于是便得证了。

Lemma 1 显然是死的 \(O(n)\),对直接求解没啥帮助。考虑优化 Lemma 2。

沿用 Lemma 1 的 Proof 中的“分块”思想。把 \(g(n)\) 相同的一段 \(n\) 分为一块,并将块长相同的几个块分为一族。显然块长为 \(i\) 的族有 \(g(i)\) 个块。

预处理一下发现 \(\sum_{i\le N} i\cdot g(i)\) 增长的很快,\(N=1.5\times 10^5\) 能做 \(10^{13}\),\(N = 1.5\times 10^7\) 可以做 \(10^{18}\)。直接用 Lemma 1 递推就行了。

预处理后,考虑直接把整个的族直接从 \(n\) 里减掉。这样就把问题转化为了某一个族里第 \(n\) 个数是第几个块里的。由于块长已经预处理出来了(并且可以随着前面减的过程算出来),直接做个除法就行。注意边界条件。

其实仔细思考可以发现,前缀族大小和就等价于 \(\{g(n)\}_{n\in\mathbb N^*}\) 的前缀和,因此说这是 Lemma 2 的优化。

注意到我们要找到最大的 \(k\) 使得 \(\sum_{i\le k}i\cdot g(i)\le n\),这个玩意可以预处理后用二分查找优化。当然不二分也可以过这题。

做完之后可以顺手切了 Project Euler 341(

code:

const int N = 1.5e5,maxn = N + 5;

ll n,g[maxn];
ll s[maxn],ans[maxn];

g[1] = 1;
for(int i = 1;i < N;i ++) g[i + 1] = g[i + 1 - g[g[i]]] + 1;
for(int i = 1;i <= N;i ++) s[i] = s[i - 1] + g[i] * i,ans[i] = ans[i - 1] + g[i];

inline ll getG(ll n) {
    if(n <= N) return g[n];
    ll i = std::upper_bound(s + 1,s + N + 1,n) - s - 1; 
    ll ss = s[i],anss = ans[i],gg = getG(anss + 1);
    return anss + (n - ss) / gg + !!((n - ss) % gg);
}

标签:10,le,题解,sum,SP8836,Lemma,maxn,SEQ7,预处理
From: https://www.cnblogs.com/resorie/p/soln-sp8836.html

相关文章

  • AtCoder Beginner Contest 266 一句话题解
    AandBsbt,不讲。C垃圾计算几何,问是不是一个凸包,搞份板子交就可以了。D简单dp,令\(f(i,j)\)表示第\(i\)个时间在第\(j\)个位置的最大价值,从上一个时间转移,可以......
  • 2021年 西南石油大学超算与并行计算团队南充校区分队 第二届招新赛题解
      2021年SWPU(南充)超算团队招新赛总体难度并不是很大,大部分题目考察的是基本的编程能力,题目中涉及到了一些并行计算相关的名词和知识,选手在参加比赛的同时,既能够展示......
  • 洛谷 P6862 [RC-03] 随机树生成器 绿 题解
    前言模数要模\(1e9+9\)!!模数要模\(1e9+9\)!!模数要模\(1e9+9\)!!结论\(n\)个点的树的形态有\((n-1)!\)个,对于节点\(k\),它的所有度数和为\((n-1)!\left(\sum\limits_{......
  • [Atcoder]ABC266题解
    C-ConvexQuadrilateral计算几何给定平面内四个点,要求判断它们组成的四边形是否是凸四边形法一:凸四边形的两条对角线将其分成两个三角形分成的两个三角形面积相加......
  • [POJ1062]昂贵的聘礼题解
    [POJ1062]昂贵的聘礼题目链接【题目大意】现有n个物品,每个物品价格为vi,同时可以用其他物品减免价格(当然,你必须拥有该物品).问如何购买可以使得到物品1的花费最少.此外,还......
  • CF1455G Forbidden Value 题解
    CF1455GForbiddenValue已知初始值\(x=0\),给定下面2种命令:set\(y\)\(v\),令\(x=y\),或花费\(v\)元钱删除该命令;if\(y\)...end,如果\(x==y\),执行if...end中的命令,否......
  • 题解 树套树
    题面二叉查找树(BST)是一种简单的数据结构,本题默认你已经熟悉BST的插入和查询两种操作。给你一棵树,每个节点有一个BST。有以下两种操作:\(u,v,k\):在路径\((u,v)\)上每......
  • AtCoder Beginner Contest 266 题解
    只有ABCDEFG的题解。A模拟。代码voidmian(){strings;cin>>s;intpos=int(s.size())/2;cout<<s[pos]<<endl;}B模拟,注意longlong。......
  • pip下载慢问题解决方案
    在使用Python开发过程中,经常要用pip安装软件包,但是直接使用pipinstallpackagename经常慢得要死,而且慢就算了很多时候还下载完成安装失败。问题原因pip默认使用的是国外......
  • P1003 [NOIP2011 提高组] 铺地毯 题解
    题目传送门[NOIP2011提高组]铺地毯题目描述为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有\(n\)......