コーディングの課題 - このソリューションはなぜ機能するのですか？

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からidxのライトがパリンドロームを形成できるように、iを数えます。つまり、各タイプの光が偶数であることを意味します。または、（回文の真ん中にある）1つを除いて、すべてのライトが偶数であることを意味します。

コードでは、O（n^2）の動作を避けるために、iを数えてトリックを使用します。インデックスidxの光を処理した後、アレイvaluesは、mごとに、i<idxの数を含み、0からiまでのライトのシーケンスは、各光の偶数または奇数（mのビットに応じて）を含む。したがって、たとえば、values[3]には、ライトの初期シーケンスの数が含まれます（最大でidx、奇数のライト0および1、および偶数の他のライト）。この配列では

は、idxで終わるシャッフル回文をカウントするのは簡単です：最大idxにマスクがmask、であるならば、すべてのライトの数が偶数で回文数はと左列の数と同じです同じマスク（すなわち：values[mask]）。同様に、奇数個の光（middle）を除いて偶数個の光を有するパリンドロームの数は、マスクmask^(1<<middle)を有する左配列の数と同じである。