[ARC135F] Delete 1, 4, 7, ... 题解

[ARC135F] Delete 1, 4, 7, ...
来自 @NobleNumbat 的好题分享。
设 \(f(n)\) 表示一次操作之后第 \(n\) 个位置上的数的值，容易发现 \(f(n)=\lfloor \frac{3n+1}{2} \rfloor\)。那么设 \(f^k(n)\) 表示 \(k\) 次操作之后第 \(n\) 个位置上的值，则 \(f^k(n)=f^{k-1}(f(n))\)。再设 \(s(k)\) 表示 \(k\) 次操作之后剩下的数的个数，则 \(s(k)=\lfloor \frac{2s(k-1)}{3} \rfloor\)。
答案就是 \(\sum_{i=1}^{s(k)} f^{k}(i)\)。
直接做是 \(O(k\cdot s(k))=O((\frac{2}{3})^kkn)\) 的，当 \(k\) 比较大（差不多 \(k>40\)）的时候可以通过。
当 \(k\) 比较小的时候，我们需要一个很牛的结论：\(f^k(n+2^k)=f^k(n)+3^k\)。

证明：考虑数学归纳法。
当 \(k=1\) 时，根据 \(f\) 的意义显然是对的。
当 \(k>1\) 时，我们有：

\[\begin{aligned}f^k(n+2^k) &= f^{k-1}(\lfloor \frac{3(n+2^k)+1}{2} \rfloor) \\           &= f^{k-1}(\lfloor \frac{3n+1}{2} \rfloor + 3\cdot 2^{k-1}) \\           &= f^{k-1}(\lfloor \frac{3n+1}{2} \rfloor) + 3\cdot 3^{k-1} \\           &= f^k(n) + 3^k \\\end{aligned}\]

这也就是说我们只需要算出所有 \(i\in [0,2^k)\) 的 \(f^k(i)\)，那么对于其他的 \(n\equiv i \pmod {2^k}\) 就都知道了。
但很可惜这个做法是 \(O(2^kk)\) 的，仍然过不了。
注意到现在问题的规模是 \(k\le 40\)，很难不想到折半，我们取两个数 \(x,y\) 满足 \(x+y=k\)，则 \(f^k(n)=f^y(f^x(n))\)。然后我们把每个数的二进制表示下的前 \(x\) 位和后面的位拆开。
大力推式子，为了方便不妨将 \(f^k(0)=0\) 也算入答案：

\[\begin{aligned}ans &= \sum_{i=0}^{s(k)} f^k(i)  \\    &= \sum_{i=0}^{2^x-1} \sum_{j=0}^{\lfloor \tfrac{s(k)-i}{2^x} \rfloor} f^k(i+2^xj) \\    &= \sum_{i=0}^{2^x-1} \sum_{j=0}^{\lfloor \tfrac{s(k)-i}{2^x} \rfloor} f^y(f^x(i+2^xj)) \\    &= \sum_{i=0}^{2^x-1} \sum_{j=0}^{\lfloor \tfrac{s(k)-i}{2^x} \rfloor} f^y(f^x(i)+3^xj)) \\\end{aligned}\]
我们设 \(F(a,b)=\sum_{j=0}^a f^y(b+3^xj)\)，则有：\(ans=\sum_{i=0}^{2^x-1} F(\lfloor \tfrac{s(k)-i}{2^x} \rfloor,f^x(i))\)。
现在只需要直到怎么快速计算 \(F(a,b)\)。
考虑类似于倍增/二进制拆分的思想，设 \(g(i,b)=\sum\limits_{j=0}^{2^i-1} f^y(b+3^xj)\)，那么在计算 \(F(a,b)\) 的时候我们先把区间 \([0,a]\) 拆分成 \(O(\log a)\) 个形如 \([l,l+2^i-1]\) 的区间，然后：

\[\begin{aligned}F(a,b) &= \sum_{j=0}^{a} f^y(b+3^xj) \\       &= \sum_{[l,l+2^i-1]} \sum_{j=l}^{l+2^i-1} f^y(b+3^xj) \\       &= \sum_{[l,l+2^i-1]} \sum_{j=0}^{2^i-1} f^y(b+3^x(l+j)) \\        &= \sum_{[l,l+2^i-1]} \sum_{j=0}^{2^i-1} f^y(b+3^xl+3^xj) \\        &= \sum_{[l,l+2^i-1]} g(i,b+3^xl) \\ \end{aligned}\]
所以我们只需要知道怎么算 \(g\) 就可以了，类似的，可以知道：

\[\begin{aligned}g(i,b) &= \sum_{j=0}^{2^i-1} f^y(b+3^xj) \\       &= \sum_{j=0}^{2^{i-1}-1} f^y(b+3^xj) + \sum_{j=2^{i-1}}^{2^i-1} f^y(b+3^xj) \\       &= \sum_{j=0}^{2^{i-1}-1} f^y(b+3^xj) + \sum_{j=0}^{2^{i-1}-1} f^y(b+3^x(j+2^{i-1})) \\       &= \sum_{j=0}^{2^{i-1}-1} f^y(b+3^xj) + \sum_{j=0}^{2^{i-1}-1} f^y(b+3^x2^{i-1}+3^xj) \\       &= g(i-1,b)+g(i-1,b+3^x2^{i-1}) \\\end{aligned}\]
所以 \(g\) 是可以递推的，但是直接记忆化复杂度是错的，因为 \(b\) 这一维是 \(O(n)\) 的。
但是当 \(b\ge 2^y\) 时，不妨设 \(b=2^yq+r(0\le r40\) 的时候用算法一，当 \(k\le 40\) 的时候用算法二就可以了。
code
[code]#include#define int long long #define Debug puts("-------------------------")#define int128 __int128using namespace std;const int N=100+5,B=40,mod=998244353,M=(1