当F(x，i)= F(x-1，i)xor F(x-1，i + 1)xor ... F(x-1，n)时如何找到F(x，0)比线性时间 [英] How to find F(x,0) when F(x,i) = F(x-1,i) xor F(x-1, i+1) xor ... F(x-1,n) in less than linear time

问题描述

鉴于基本数组，我需要计算以下给出的函数的值:

Given a base array, I need to compute the value of a function given below:

A[] = { a0, a1, a2, a3, .. an }

F(0,i) = ai  [Base case] 

F(1,i) = F(0,i) xor F(0,i+1) xor F(0,i+2) ... xor F(0,n)
F(2,i) = F(1,i) xor F(1,i+1) xor F(1,i+2) ... xor F(1,n)
.
.
F(x,i) = F(x-1,i) xor F(x-1,i+1) xor F(x-1,i+2) ... xor F(x-1,n)

0 < x < 10^18
0 < n < 10^5

我需要找到 F(x，0).

过去3天，我一直在努力解决这个问题.我未能对其进行优化，无法提出可行的解决方案.任何在小于线性时间内找到F(x，0)的帮助都将受到赞赏.

I am trying to solve this equation for the past 3 days. I have failed to optimise it and come up with a feasible solution. Any help to find F(x,0) in less than linear time is appreciated.

我的观察(如果有任何重要意义):

My observation (if it is of any importance) :

F(0,0) = a0
F(1,0) = a0^a1^a2^a3 ....
F(2,0) = a0^a2^a4 ....
F(3,0) = (a0^a4^a8...) ^ (a1^a5^a9...)
F(4,0) = a0^a4^a8 ....
F(5,0) = (a0^a1^a2^a3) ^ (a8^a9^a10^a11) ^ (a16^..a19) ^ ...
F(6,0) = (a0^a8^a16...) ^ (a2^a10^a18...)
F(7,0) = (a0^a8^a16...) ^ (a1^a9^a17...)
F(8,0) = a0^a8^a16^ ....

推荐答案

如果通过递归关系反转数组，也许会变得更容易

Maybe it becomes easier if you reverse the array, with the recurrence relation

F(0, i) = a[n-i]
F(x, i) = XOR[0 <= j < i]( F(x-1, j) )

，即从0到i而不是i到n.然后，我们正在寻找F(x, n).如果我们做一张桌子:

that is, going from 0 to i instead of i to n. We are then looking for F(x, n). If we make a table:

  | 0        1           2                              3
--+-------------------------------------------------------------------------------------------
0 | A=a[n]   B=a[n-1]    C=a[n-2]                       D=a[n-3]
1 | A        A^B         A^B^C                          A^B^C^D
2 | A        A^(A^B)     A^(A^B)^(A^B^C)                A^(A^B)^(A^B^C)^(A^B^C^D)^B^C^D
3 | A        A^(A^(A^B)) A^(A^(A^B))^(A^(A^B)^(A^B^C))  A^(A^(A^B))^(A^(A^B)^(A^B^C))^(A^(A^B)^(A^B^C)^(A^B^C^D))

或者让我们停止使用XOR符号，只计算每个术语出现的频率:

or let's stop using the XOR sign and just count how often each term appears:

  | 0   1     2        3           4
--+-----------------------------------------------
0 | 1A    1B       1C          1D             1E
1 | 1A  1A1B   1A1B1C   1A 1B1C1D   1A 1B 1C1D1E
2 | 1A  2A1B   3A2B1C   4A 3B2C1D   5A 4B 3C2D1E
3 | 1A  3A1B   6A3B1C  10A 6B3C1D  15A10B 6C3D1E
4 | 1A  4A1B  10A4B1C  20A10B4C1D  35A20B10C4D1E

我们还可以看到递归关系与

We can also see that the recurrence relation is the same as

F(x, i) = F(x-1, i) + F(x, i-1)

这是帕斯卡三角形.具体来说，我们追求的值是第 n 个对角线，当然可以是

This is Pascal's Triangle. Specifically, the values we are after are the nth diagonal, which can of course be calculated on its own. Then check whether the number is even or odd, so that you know whether the XOR operations on that element cancel themselves out or not.

这篇关于当F(x，i)= F(x-1，i)xor F(x-1，i + 1)xor ... F(x-1，n)时如何找到F(x，0)比线性时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！