Это можно сделать в O (N) с использованием dynamici c, программируя .
Допустим, dp[i][j] - это ряд массивов, таких, что они имеют i элементов и их XOR-сумма равна j.
Обратите внимание, что 0 <= j <= 7, потому что если N == 6 array [1, 2, 4, 4, 2, 1] соответствует, но его префикс [1, 2, 4] имеет XOR-сумму 7. Кроме того, вы не можете получить сумму XOR больше 7, потому что все числа в диапазоне от 0 до 5 не могут иметь никаких других терминов, кроме 2 ^ 2, 2 ^ 1 и 2 ^ 0, когда разложены в степени 2.
Вот формула для вычисления dp[i][j] с использованием ранее вычисленных значений:
dp[i][j] = 0
# k is XOR-sum of previously calculated number of arrays of length i-1.
for k in range(0, 8):
# x is a number we append to arrays of length i-1 so XOR-sum is j.
x = j xor k
if x <= 5:
dp[i][j] += d[i - 1][k]
И это остаток кода:
# Assume there's a two dimensional array of integers dp of size N+1 x 8.
# Dynamics initialization.
# There's only one possible array of length 0: []. It's XOR-sum is 0.
dp[0][0] = 1
for i in range(1, 8):
dp[0][i] = 0
# Dynamics state calculation.
for i in range(1, N+1):
for j in range(0, 8):
# Here comes code from above.
dp[i][j] = 0
for k in range(0, 8):
x = j xor k
if x <= 5:
dp[i][j] += d[i - 1][k]
# Answer is dp[N][0].
print(dp[N][0])
Расчет состояния динамики составляет N * 8 * 8 итераций, поэтому сложность составляет O (N) (обратите внимание, что, несмотря на линейную сложность, константа 64 может быть довольно большой).
Есть способ сделать это должно быть вычислено в O (log N) с использованием матричного двоичного возведения в степень . Вкратце: вам нужно вычислить матрицу 8x8 M, показывающую, как значения dp[i-1][*] превращаются в значения dp[i][*]; затем вычислите dp[0] * M^N, где dp[0] равно [1, 0, 0, 0, 0, 0, 0, 0] (точно так же, как при инициализации динамики).