PAM板子题

思路：所有的回文串长度好统计，manacher或者PAM都可以做，难点在于统计回文串内的字符种类
观察PAM中的增加字符的add函数的代码 
// 节点：0为偶根，1为奇根。从2开始是有效节点。
      int nxt[N][26];         // 类似Trie的指针
      int fail[N];         // 失败指针/后缀链接
      int len[N];          // 节点代表的回文串长度
       int cnt[N];          // 节点代表的回文串出现次数（最后需要count函数统计）
      int num[N];          // 以当前节点为结尾的回文串个数（沿着fail链）
      int s[N];            // 存放添加的字符
      int last;               // 最后一个字符所在的节点
      int n;                  // 已添加的字符数
      int tot;                // 总的节点数（2 ~ tot）
    
        void add(int c) {
        c -= 'a'; // 根据实际情况调整，如果输入是数字则不需要此句
        s[++n] = c;
        int cur = getFail(last); // 通过上一个节点的last找到可扩展的节点cur
        if (!nxt[cur][c]) {
            // 如果这个回文串还没有出现过，需要新建节点
            int now = newNode(len[cur] + 2); // 新回文串长度是cur的长度+2

            // 设置新节点的fail指针
            // 从cur的fail节点开始，继续找可以扩展的后缀
            fail[now] = nxt[getFail(fail[cur])][c];
            // 注意：如果ch[getFail(fail[cur])][c]不存在怎么办？
            // 由于奇根和偶根的存在，它一定会存在。最坏情况会指向单个字符c或空串。
            nxt[cur][c] = now; // 将cur的c孩子指向新节点
            num[now] = num[fail[now]] + 1; // 更新以新节点结尾的回文串个数
        }
        last = nxt[cur][c]; // 更新last
        cnt[last]++;       // 对这个节点的出现次数计数+1
        // 注意：此时的cnt并不是最终的出现次数，还需要最后通过count函数累加
    }
我们发现，函数内的cur节点是待添加字符c将要对其插入的节点，now是待添加字符c的新节点，相当于从cur结尾的回文串加了一种字符c，变成了now结尾的回文串，而我们又要统计字符种类，看c只有26种，考虑状态压缩
可以开一个数组col，在这上面执行 col[now] = (col[cur] | (1<<c)); 语句，相当于把字符种类压入至一个二进制数中
统计答案时，这个二进制数上的1的个数就是答案
这里推荐c++的函数__builtin_popcount(num)，能够快速统计num在二进制下的1的个数，不用自己手写函数了

主函数如下 
struct Palindromic_Tree { //仅小写字符 
    // 节点：0为偶根，1为奇根。从2开始是有效节点。
    int nxt[N][26]; 		// 类似Trie的指针
    int fail[N];         // 失败指针/后缀链接
    int len[N];          // 节点代表的回文串长度
    int cnt[N];          // 节点代表的回文串出现次数（最后需要count函数统计）
    int num[N];          // 以当前节点为结尾的回文串个数（沿着fail链）
    int s[N];            // 存放添加的字符
    int last;               // 最后一个字符所在的节点
    int n;                  // 已添加的字符数
    int tot;                // 总的节点数（2 ~ tot）
    int col[N];
    // 总的不同回文子串个数就是 pam.tot - 2

    int newNode(int L) {
        // 初始化一个新节点，长度为L
        Forl(i,0,25){
        	nxt[tot][i]=0;
		}
        cnt[tot] = num[tot] = 0;
        len[tot] = L;
        return tot++;
    }

    void init() {
        // 初始化整个PAM
        tot = 0;
        n = last = 0;
        // 创建两个根节点：偶根0 和 奇根1
        newNode(0);   // 偶根，长度为0
        newNode(-1);  // 奇根，长度为-1（虚拟节点）
        s[0] = -1;    // 设置第一个字符为特殊字符，防止越界
        fail[0] = 1;  // 偶根的fail指向奇根
        fail[1] = 1;  // 奇根的fail指向自己
    }

    int getFail(int x) {
        // 从x节点开始，沿着fail链向上找，直到找到满足条件的节点
        // 条件：s[n - len[x] - 1] == s[n]
        while (s[n - len[x] - 1] != s[n]) {
            x = fail[x];
        }
        return x;
    }

    void add(int c) {
        c -= 'a'; // 根据实际情况调整，如果输入是数字则不需要此句
        s[++n] = c;
        int cur = getFail(last); // 通过上一个节点的last找到可扩展的节点cur
        if (!nxt[cur][c]) {
            // 如果这个回文串还没有出现过，需要新建节点
            int now = newNode(len[cur] + 2); // 新回文串长度是cur的长度+2

            // 设置新节点的fail指针
            // 从cur的fail节点开始，继续找可以扩展的后缀
            fail[now] = nxt[getFail(fail[cur])][c];
            // 注意：如果ch[getFail(fail[cur])][c]不存在怎么办？
            // 由于奇根和偶根的存在，它一定会存在。最坏情况会指向单个字符c或空串。

            col[now]=(col[cur]|(1<<c)); //压入字符种类

            nxt[cur][c] = now; // 将cur的c孩子指向新节点
            num[now] = num[fail[now]] + 1; // 更新以新节点结尾的回文串个数
        }
        last = nxt[cur][c]; // 更新last
        cnt[last]++;       // 对这个节点的出现次数计数+1
        // 注意：此时的cnt并不是最终的出现次数，还需要最后通过count函数累加
    }

    void count() {
        // 统计每个回文串的真实出现次数
        // 因为一个长回文串的出现次数会包含它的所有回文后缀的出现次数
        // 所以需要按len从大到小遍历，累加到fail指针指向的节点上
        Forr(i,tot-1,2) { // 从编号大的节点开始（长度也大）
            cnt[fail[i]] += cnt[i];
        }
        // 注意：两个根节点（0和1）的cnt无实际意义，通常从2开始使用。
    }
}PAM;

char str[N];
int Lstr;

void InfiniteLight() {
    read(str+1);
    Lstr=strlen(str+1);
    PAM.init();
    Forl(i,1,Lstr) {
        PAM.add(str[i]);
    }
    PAM.count();
    long long totnum=0;
    Forl(i,2,PAM.tot-1) {
        totnum+=(long long)__builtin_popcount(PAM.col[i])*PAM.cnt[i]; //计算答案
    }
    println(totnum);
    return ;
}