[ARC137] D - Prefix XORs

[Q] https://atcoder.jp/contests/arc137/tasks/arc137_d

メモ化再帰で O(NlogN)。
本番TLEでとても悔しい。処理の高速化は十分だったけど、下処理が2つ足りていなかった。
1. メモをmapでしてしまったのでlogN増え、
2. log2()とかpow()を使ったのでlogN増えた。
N=M=100000なら十分間に合っていた。悔しい…。

・考察
とりあえずN=7 M=9 のすべての遷移を表示し観察。

N=7 M=9
A[]: 1 2 4 8 16 32 64

N:          0       1       2       3       4       5       6
cycle:      1       2       4       4       8       8       8
A[0]: 0000001 0000010 0000100 0001000 0010000 0100000 1000000 
A[1]: 0000001 0000011 0000111 0001111 0011111 0111111 1111111 
A[2]: 0000001 0000010 0000101 0001010 0010101 0101010 1010101 
A[3]: 0000001 0000011 0000110 0001100 0011001 0110011 1100110 
A[4]: 0000001 0000010 0000100 0001000 0010001 0100010 1000100 
A[5]: 0000001 0000011 0000111 0001111 0011110 0111100 1111000 
A[6]: 0000001 0000010 0000101 0001010 0010100 0101000 1010000 
A[7]: 0000001 0000011 0000110 0001100 0011000 0110000 1100000 
A[8]: 0000001 0000010 0000100 0001000 0010000 0100000 1000000 
A[9]: 0000001 0000011 0000111 0001111 0011111 0111111 1111111 

1. 各Nについて、周期があることがわかる。
N=0で1周期 (1)
N=1で2周期 (10->11)
N=2,3で4周期 (100->111->101->110)
N=4,5,6,7で8周期。(10000->11111->10101->11001->10001->11110->...)​
この先も、1, 2, 44, 8888,16*8 ,32*16...の周期になるんだろう。

周期での高速化ができるので、N=6について。
A(6, 0) = 1000000 は
A(6, 8) = 1000000 になる。
A(6, 16) = 1000000 になる。

他にも
A(6,1) = A(6,9) = A(6,17)...になる
A(6,2) = A(6,10) = A(6,18)...になるだろう。

2. 周期以外の法則を見つける
求めたいA(x, y)は、Aから上に2の累乗移動した場所と、Aから左に2の累乗移動した場所との、XORになっている。
A(x, y) = A(x-d, y) ^ A(x, y-d)

N:          0       1       2       3       4       5       6
cycle:      1       2       4       4       8       8       8
A[0]: 0000001 0000010 0000100 0001000 0010000 0100000 1000000 
A[1]: 0000001 0000011 0000111 0001111 0011111 0111111 1111111 
A[2]: 0000001 0000010 0000101 0001010 0010101 0101010 1010101 
A[3]: 0000001 0000011 0000110 0001100 0011001 0110011 1100110 
A[4]: 0000001 0000010 0000100 0001000 0010001 0100010 1000100 
A[5]: 0000001 0000011 0000111 0001111 0011110 0111100 1111000 
A[6]: 0000001 0000010 0000101 0001010 0010100 0101000 1010000 
A[7]: 0000001 0000011 0000110 0001100 0011000 0110000 1100000 
A[8]: 0000001 0000010 0000100 0001000 0010000 0100000 1000000 
A[9]: 0000001 0000011 0000111 0001111 0011111 0111111 1111111 


1. A(6,0) = 1000000
これは入力からすぐ求まる。

2. A(6,1) = 1111111 を求める。
これは A(5,1)^A(6,0)になっている。

3. A(6,2) = 1010101 を求める。
これは A(4,2)^A(6,0) になっている。

4. A(6,3)は、A(4,3)^A(6,1)
5. A(6,4)は、A(2,4)^A(6,0)
6. A(6,5)は、A(1,5)^A(6,1)...

整理すると
1. A(6,0): 入力
2. A(6,1): A(5,1)^A(6,0) = A(6-1,1)^A(6,1-1)
3. A(6,2): A(4,2)^A(6,0) = A(6-2,2)^A(6,2-2)
4. A(6,3): A(4,3)^A(6,1) = A(6-2,3)^A(6,3-2)
5. A(6,4): A(2,4)^A(6,0) = A(6-4,4)^A(6,4-4)
6. A(6,5): A(2,5)^A(6,1) = A(6-4,5)^A(6,5-4)
7. A(6,6): A(2,6)^A(6,2) = A(6-4,6)^A(6,6-4)
8. A(6,7): A(2,7)^A(6,3) = A(6-4,7)^A(6,7-4)

求めたいA()は、Aから上と左に2の累乗移動した場所との、XORになっている。

・A(6,6) は A(6,2)^A(2,6)で求まる

N:          0       1       2       3       4       5       6
cycle:      1       2       4       4       8       8       8
A[0]: 0000001 0000010 0000100 0001000 0010000 0100000 1000000 
A[1]: 0000001 0000011 0000111 0001111 0011111 0111111 1111111 
A[2]: 0000001 0000010 0000101 0001010 0010101 0101010<1010101> 
                                                      ~~~~~~~ A(6,2)
A[3]: 0000001 0000011 0000110 0001100 0011001 0110011 1100110 
A[4]: 0000001 0000010 0000100 0001000 0010001 0100010 1000100 
A[5]: 0000001 0000011 0000111 0001111 0011110 0111100 1111000 
A[6]: 0000001 0000010<0000101>0001010 0010100 0101000<1010000>
                      ~~~~~~~ A(2,6)                  ~~~~~~~ A(6,6)
A[7]: 0000001 0000011 0000110 0001100 0011000 0110000 1100000 
A[8]: 0000001 0000010 0000100 0001000 0010000 0100000 1000000 
A[9]: 0000001 0000011 0000111 0001111 0011111 0111111 1111111 

この2つの法則で高速化すればO(NlogN)。
Q. メモ化はvector?
A. メモをmapでやるとTLE。

Q. 2の累乗をpow()とかlog2()とかで計算？
A. logNの処理になるのでTLE。前計算必須。

実装

ll N, M;
vector<ll> A;
ll B[1000100]; // 前計算1
ll D[1000100]; // 前計算2
ll cnt; // debug
vector<ll> memo[1000100];

void initB() {
 // B
 // 0:1
 // 1:2
 // 2:4
 // 3:4
 // 4:8
 ll nx = 1;
 for (ll i = 1; i <= N; ++i) {
   while (nx < i) nx *= 2;
   B[i - 1] = nx;
 }

 // D
 // 0:0
 // 1:1
 // 2:2
 // 3:2
 // 4:4
 nx = 1;
 for (ll i = 1; i < N; ++i) {
   while (nx * 2 <= i) nx *= 2;
   D[i] = nx;
 }
}

ll dfs(ll x, ll y) {
 ++cnt;
 // 周期の高速化
 y %= B[x];
 if (x == 0) return A[0];
 if (y == 0) return A[x];
 if ((ll)memo[x].size() > y) return memo[x][y];
 ll p = min(x, y);
 ll d = D[p];
 // 上に2^maxしたものと、左に2^maxしたものとのXORをとる
 ll ret = dfs(x - d, y) ^ dfs(x, y - d);
 memo[x].push_back(ret);
 return ret;
}

int main() {
 cincout();

 cin >> N >> M;
 initB();
 A.resize(N);
 rep(i, N) cin >> A[i];
 rep(i, N) { memo[i].push_back(A[i]); }

 rep(m, M) { cout << dfs(N - 1, m + 1) << " \n"[m == M - 1]; }
 // cerr << cnt << endl;
}

https://atcoder.jp/contests/arc137/submissions/30250173