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