Colorful String（2019徐州网络赛）（回文自动机上dfs+状压）

Colorful String

比赛一开，我看的第一题就是这题。然后一看，回文串！那肯定回文自动机搞一下不就行了吗？再仔细一看，发现有个小地方我不敢确定，遂想用 $manacher$manacher水过去，想了一小会，发现不好实现，于是又转战回文自动机。由于当时一下子想不起来回文自动机的两棵树的转移边有没有交叉的，马上去找了篇博客看一下树的形态。发现，嗯，应该是没有交叉的。于是马上敲了一个 $dfs$dfs+状压，结果写的有点问题，费了点劲过了样例， $18mis$18mis $1A$1A，舒服！

题意：设一个回文串的贡献为其包含的不同字符的个数，则给出一个原串，求其所有回文子串的贡献之和

思路：

1. 先建好的回文自动机，由于两棵树可以认为是独立的，因此分别从 $0$0和 $1$1节点进行 $dfs$dfs即可遍历完所有的回文串
2. 在遍历的过程中，将所包含的不同字符的状态压缩在一个 $int$int变量中，因此统计答案就很简单了
3. 哈哈，似乎很模板！

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 3e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int ch[maxn][26], fail[maxn], len[maxn], cnt[maxn];
int last, sz, pos;

void init() { //我的回文自动机初始化可能跟别人的不一样，但原理是一样的
    fail[0]=fail[1]=sz=last=1;
    len[1]=pos=-1;
}

void add(int c) {
    ++pos; int p=last;
    while(s[pos-len[p]-1]!=s[pos]) p=fail[p];
    if(!ch[p][c]) {
        int np=++sz, fp=fail[p];
        len[np]=len[p]+2;
        while(s[pos-len[fp]-1]!=s[pos]) fp=fail[fp];
        fail[np]=ch[fp][c];
		ch[p][c]=np;
    }
    last=ch[p][c];
    cnt[last]++;
}

ll ans=0;

void dfs(int now, int state, int c) {
    for(int i=0; i<26; ++i) {
        if(ch[now][i]) {
            int nc=c, nstate=state;
            if((state&(1<<i))==0) nstate|=1<<i, nc++;
            ans+=nc*cnt[ch[now][i]];
            dfs(ch[now][i],nstate,nc);
        }
    }
}

int main() {
    //ios::sync_with_stdio(false);
    scanf("%s", s);
    init();
    for(int i=0; s[i]; ++i) add(s[i]-'a');
    for(int i=sz; i; --i) cnt[fail[i]]+=cnt[i];
    dfs(0,0,0), dfs(1,0,0);
    printf("%lld\n", ans);
}