Codility challenge -이 솔루션은 왜 작동합니까?

Question

문제 :

숫자의 문자열이 주어진다면, 임의의 회문의 아나그램 인 서브 워드 (일관된 서브 시퀀스)의 수를 계산하십시오.

예 :

입력 문자열

"02002"이 결과는 11이어야, 즉 :

"0", "2", "0", "0", "2", "00 ","020 ","200 ","002 ","2002 ","02002 "

아래의 해결책을 볼 수는 있지만 그 이유는 알 수 없습니다. 특히 내부 루프의 요점을 이해하지 못합니다. 아무도이 뒤에 논리를 설명 할 수 있습니까? https://codility.com/programmers/task/winter_lights/ :

#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; 
} 

자세한 내용은에서 필요한 경우. 당신이 i에서 idx에 조명이 회문을 형성 할 수 있다는 i는 계산하려는 각 idx를 들어

Answer 1

. 즉, 각 유형의 빛이 짝수 개임을 의미하거나, 하나를 제외하고는 모든 조명이 짝수입니다 (회귀선 중간에 위치).

코드는 O (n^2) 동작을 피하기 위해 트릭을 사용하여 i을 계산합니다. 인덱스 idx에서 빛을 처리 한 후 배열 values에는 각 m에 대해 i<idx의 숫자가 포함되어 0 ~ i의 조명 시퀀스에는 각 조명의 짝수 또는 홀수 (m의 비트에 따라 다름)가 포함됩니다. 예를 들어, values[3]에는 조명의 초기 시퀀스 수가 포함됩니다 (최대, 홀수는 0 번과 1 번 홀수, 짝수는 다른 라이트입니다). 이 배열

은 idx에서 끝나는 셔플 회문를 계산하는 것은 간단하다 : 최대 idx에 마스크 mask이면 모든 조명 짝수 회문의 수와 좌측 시퀀스의 수와 동일 동일한 마스크 (예 : values[mask]). 유사하게, 홀수 번째 빛 (middle)을 제외한 짝수 개의 빛을 가진 회문수의 수는 마스크 mask^(1<<middle)을 가진 왼쪽 시퀀스의 수와 동일합니다.