一道模拟赛题

一种我不太会优化的做法。感觉醍醐灌顶了。

链接：https://www.mxoj.net/problem/P130021?contestId=195

人话题意：对值域在 \([1,2^n-1]\) 的严格上升序列计数，要求不能存在连续三个位置使得异或和为 \(0\)。\(n\leq 10^6\)。

首先注意到，设 \(i\) 的二进制最高位是 \(h(i)\)，产生矛盾的位置二进制最高位只可能形如 \(h_0,h_1,h_1\)。考虑对这个东西计数。令 \(f_i\) 代表当前二进制最高位为 \(i\) 时合法的方案数。以下默认在 \(O(\log mod)\) 时间内求 \(2^{2^x}\)，无非是将指数对 \(\varphi(mod)\) 取模。

考虑转移 \(f_j\to f_i\)，即上一个最高位是 \(j\)，当前最高位是 \(i\) 的转移系数。用总方案数减去不合法的方案数。总方案数显然是 \(2^{2^{i}}-1\)。考察不合法位置的形态，设这一段开头两个数是 \(a\) 和 \(b\)，由于异或和要为 \(0\)，所以 \(ab\) 在 \(j+1\sim i\) 这一段二进制上必然完全相同，而 \(b>a\) 告诉我们 \(b\) 在 \(j\) 这一位上为 \(1\)。

因为宇宙射线，将上文的 \(b\) 替换为 \(x\)。显然 \(x\) 只需要满足 \(j\) 这一位上为 \(1\)，前面的 \(a\) 自然会存在并小于 \(x\)。那么我们实际上要计数的就是：

\[\sum\limits_{x}2^{2^{i}-1-x} \]

这个东西的样子十分变态！做一些基础的变形得到 \(2^{2^{i}-1}\sum\limits_{x}\frac1{2^x}\)。我们的想法是尽量往等比数列求和上靠拢。对 \(x\) 做二进制拆分后必定包含 \(2^j\) 项，于是即为 \(\frac1{2^{2^j}}\sum\limits_{y}\frac1{2^y}\)。后面的式子实际的组合意义就是，从 \(\frac1{2^{2^0}},\frac1{2^{2^1}},\dots,\frac1{2^{2^{j-1}}},\frac1{2^{2^{j+1}}},\dots,\frac1{2^{2^{i-1}}}\) 中选择若干个乘起来的和。我们将其分成两部分，两部分分别求和后再乘起来。

前面的部分是容易的，实际上就是 \(\sum\limits_{k=0}^{2^j-1}2^{-k}\)，等比数列求和解决。后面的部分类比一下，将其写作 \((2^{2^{j+1}})^{-2^k}\) 的形式，\(k\) 从 \(0\) 取到 \(i-j-2\)。等价于求 \(\sum\limits_{k=0}^{2^{i-j-1}-1}(2^{2^{j+1}})^{-k}\)，同样等比数列求和解决。

这样我们得到了一个时间复杂度 \(O(n^2\log mod)\) 的做法。

梦熊评测机怎么这么慢，\(n\leq 1000\) 还给我挂了十分。