G - Strange Mirroring 解説 by MMNMM

クエリあたりの演算回数を O(log log w) とする解法

\(S\) の長さを \(N\) とし、\(N,Q\) および各 \(K _ i\) が \(1\) ワードに収まる整数であると仮定して、各 \(K _ i\) ごとに \(O(\log\log w)\) 回の演算で答えを求める方法について解説します。

公式解説と同様の考察を経ることで、\(\left\lfloor\dfrac{K _ i}N\right\rfloor\) に立っているビットが奇数個か偶数個かを判定するパート以外は定数回の演算で行うことができることがわかります。

以下、\(w\operatorname{bit}\) の整数 \(x\) に対して、\(4+2\bigl\lceil\log _ 2(\log _ 2w-\log _ 2\log _ 2w+o(1))\bigr\rceil\) 回の演算で \(x\) に立っているビットの本数の偶奇を求める方法を解説します。

まず、\(w\leq 2 ^ k2 ^ {2 ^ k}\) が成り立つ非負整数 \(k\) をとります。 また、\(M=1+2 ^ {2 ^ k}+2 ^ {2\times2 ^ k}+\cdots+2 ^ {\lfloor(w-1)/{2 ^ k}\rfloor 2 ^ k}\) とします。
次のアルゴリズムを考えます。

  1. \(i=0,1,\ldots,k-1\) について、以下を行う。
    • \(w\leftarrow w\oplus w/2 ^ {2 ^ i}\) とする（ここで、\(\oplus\) はビットごとの排他的論理和とする）。
  2. \(w\leftarrow w\;\&\; M\) とする（ここで、\(\&\) はビットごとの論理積とする）。
  3. \(w\times M\) の \(\left\lfloor\dfrac{w-1}{2 ^ k}\right\rfloor2 ^ k\operatorname{bit}\) めが求める値である。

これは、ワードサイズの演算を \(2k+4\) 回行うことで実現できます。

まず、これが正しい偶奇を与えることを示します。

証明

補題

はじめの \(w\) と、整数 \(n\) について、\(w _ n=\left\lfloor\dfrac w{2 ^ {n2 ^ k}}\right\rfloor\bmod{2 ^ {2 ^ k}}\) と定める。

2 番目のステップが終了した時点における \(w\) について、以下の \(2\) つが成り立つ。

  1. \(2 ^ {n2 ^ k}\operatorname{bit}\) めの形として表されるビット以外は立っていない。
  2. \(2 ^ {n2 ^ k}\operatorname{bit}\) めは、\(w _ n\) の立っているビットが奇数個のとき、かつそのときに限り立っている。
補題の証明

\(M _ i=1+2 ^ {2 ^ i}+\cdots+2 ^ {\lfloor(w-1)/2 ^ i\rfloor2 ^ i}\) として、1. のループを繰り返すたびはじめに \(w\leftarrow w\;\&\;M _ i\) としているとしても答えが変わらないことが示せます。

すると、それぞれ帰納法によって示すことができます。

\(w\times M\) の \(\left\lfloor\dfrac{w-1}{2 ^ k}\right\rfloor2 ^ k\operatorname{bit}\) めがどのような値になるか考えてみましょう。

\(p _ n\) を \(w _ n\) の立っているビットが奇数個なら \(1\) 、そうでなければ \(0\) であるようなものとします。 2 番目のステップが終了した時点で、\(\displaystyle w=\sum _ n2 ^ {n2 ^ k}p _ n\) となっていることに注意してください。

まず、\(\left\lfloor\dfrac{w-1}{2 ^ k}\right\rfloor2 ^ k\operatorname{bit}\) めへの繰り上がりが生じることはないことが示せます（積を筆算のように整理するとよいでしょう）。

ここから、このビットが立っているかどうかは、\(p _ n\) のうち奇数個が \(1\) であるかと同値になります。 これは、\(w\) のビットのうち奇数個が経っていることと同値であり、正しい答えが得られることがわかりました。\(\square\)

よってこれを実装することでクエリごとに \(O(\log\log w)\) 回の演算で答えを求めることができます（\(k=\bigl\lceil\log _ 2(\log _ 2w-\log _ 2\log _ 2w+o(1))\bigr\rceil\) と評価することは、Lambert の W 関数に関する評価などを使うことでできます。\(\lceil\log _ 2\log _ 2w\rceil\) で上からおさえられるのはほぼ明らかです）。 \(w=64\) のとき、\(k=2\) として正しい答えを求めることができます。

実装例は以下のようになります。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string S;
    cin >> S;
    unsigned Q;
    cin >> Q;

    unsigned long N = size(S);

    for (unsigned i = 0; i < Q; ++i) {
        unsigned long K;
        cin >> K;
        --K;
        // 何周期目の何文字目かを求める
        unsigned long repeat = K / N, offset = K % N;
        // 周期の情報から大文字小文字が入れ替わっているかを求める
        unsigned long parity = repeat;
        parity ^= parity >> 1;
        parity ^= parity >> 2;
        parity &= 0x1111111111111111UL;
        parity = 1 & (parity * 0x1111111111111111UL >> 60);
        
        // parity が 1 なら大文字小文字を入れ替える
        putchar(S[offset] ^ 32 * parity);
        putchar(32);
    }

    return 0;
}

投稿日時:
最終更新: