Codility 挑战 - 为什么这个解决方案有效？

Question

问题:

给定一串数字，计算是任何回文的字谜的子词(一致的子序列)的数量。

例子:

对于输入字符串“02002”，结果应该是 11，即:

“0”、“2”、“0”、“0”、“2”、“00”、“020”、“200”、“002”、“2002”、“02002”

我可以看到下面的解决方案有效，但我不明白为什么。特别是我不明白内循环的意义。谁能解释一下这背后的逻辑？

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define M 1000000007
#define COLORS 10
#define SUBSETS (1 << (COLORS))

int solution(char *S) {
    int len, result;
    int *values;
    int v, idx, middle, mask;

    result = 0;
    values = calloc(SUBSETS, sizeof(int));
    //new_values = calloc(SUBSETS, sizeof(int));
    len = strlen(S);
    mask = 0;

    for (idx = 0; idx < len; idx++) {
        v = S[idx] - '0';
        mask ^= (1 << v);
        values[mask ^ (1 << v)] += 1;
        result = (result + values[mask]) % M;
        for (middle = 0;  middle < COLORS; middle++) {
            result = (result + values[mask ^ (1 << middle)]) % M;
        }
    }
    return result;
}

如果需要更多详细信息，请访问:https://codility.com/programmers/task/winter_lights/ .

Answer 1

对于每个 idx你想数i这样来自 i 的灯至 idx可以形成回文。这意味着每种类型的光的数量都是偶数，或者除了一个(位于回文的中间)之外的所有光的数量都是偶数。

代码使用了一个技巧来计算 i ，以避免 O(n^2) 行为。处理索引处的光后 idx , 数组 values包含每个 m , 数量 i<idx这样灯的顺序从 0 到 i包含每个灯的偶数或奇数(取决于 m 的位)。例如，values[3]包含初始灯序列的数量(最多 idx，灯 0 和 1 的数量为奇数，其他灯的数量为偶数)。

使用这个数组，计算以 idx 结尾的打乱的回文数很简单:如果掩码达到 idx是mask ，则所有灯的偶数个回文数与具有相同掩码的左序列数相同(即:values[mask])。类似地，除了奇数个光(middle)之外，具有偶数个光的回文数与掩码为mask^(1<<middle)的左序列数相同。 .