思路:

令\(f[S]\)表示集合S形成连通图的方案数,\(g[s]\)表示集合S内部任意连边的方案数.

显然:

\[g[S]=\prod_{i,j\in{S},i<j}c_{i,j}+1\]

这个我们可以在\(O(2^n{n^2})\)的复杂度内算出来.

接下来考虑计算\(f[S]\).

我们用总数减去不连通的图的个数.

假设\(x\in{S}\),我们不妨枚举所有\(S\)的真子集\(S'\),其中\(S'\)就代表包含\(x\)的一个连通块,\(S-S'\)均与\(x\)不连通.

那么\(f[S']\)我们已经算过了,剩下的\(S-S'\)就利用我们之前预处理的随意连边的\(g\)数组.

于是我们得到转移:

\[f[S]=\sum_{S'\subset{S},x\in{S'}}f[S']g[S-S']\]

这个过程是\(O(3^n)\).

然后我们就在\(O(2^n{n^2}+3^n)\)的时间内解决了这题.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
#define N 16
 
int f[1<<N],g[1<<N],h[1<<N],c[N][N];
static const int mod=(1e9)+7;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
 
#define p(S,x) (((S)>>(x))&1)
 
int main(){
    int n;scanf("%d",&n);register int i,j,k;
    for(i=0;i<n;++i)for(j=0;j<n;++j)scanf("%d",&c[i][j]);
    for(i=0;i<n;++i)f[1<<i]=g[1<<i]=1;
    for(i=1;i<(1<<n);++i)h[i]=h[i^(i&-i)]+1;
    for(i=1;i<(1<<n);++i){
        if(h[i]==1)continue;
        else{
            g[i]=1;
            for(j=0;j<n;++j)for(k=j+1;k<n;++k)if(p(i,j)&&p(i,k))
                g[i]=(LL)g[i]*(c[j][k]+1)%mod;
            int ins;
            for(j=0;j<n;++j)if(p(i,j)){ins=j;break;}
            for(int mas=(i-1)&i;mas;mas=(mas-1)&i)if(p(mas,ins))
                inc(f[i],(LL)f[mas]*g[i^mas]%mod);
            f[i]=(g[i]>=f[i])?g[i]-f[i]:g[i]+mod-f[i];
        }
    }
    printf("%d",f[(1<<n)-1]);
    return 0;
}

思路:

首先我的思路十分傻叉,是\(f[i][j][k]\)表示长度为\(i\),在自动机上的节点为\(j\),包含子串的状态为\(k\)可不可能.但这样复杂度直接爆炸.

但是我们可以令\(f[i][j]\)表示在自动机上的节点为\(i\),包含子串的状态为\(j\)时的最短长度.

这样我们就转化成了边权均为1的单源最短路,BFS就行了.

若按照字母字典序从小到大的顺序进行BFS,得出的就是字典序最小的答案了.

(有点卡内存)

(话说我一开始AC自动机都写错,没治了)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 12
#define L 610
 
short ch[L][26],end[L],pre[L],cnt;
 
char s[L];
 
int q[L],fr,ta;
short lastchar[L*(1<<N)];
int laststate[L*(1<<N)];
short state[L*(1<<N)];
short ins[L*(1<<N)];
bool vis[L][1<<N];
 
char ans[L];int id;
 
int main(){
    int n;scanf("%d",&n);register int i,j;
    int p,y;
    for(i=1;i<=n;++i){
        scanf("%s",s);int len=strlen(s);
        for(p=j=0;j<len;++j){
            if(!ch[p][y=s[j]-'A'])ch[p][y]=++cnt;p=ch[p][y];
        }end[p]|=1<<(i-1);
    }
    for(j=0;j<26;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<26;++j)if(ch[u][j]){
            for(q[ta++]=v=ch[u][j],r=pre[u];r&&!ch[r][j];r=pre[r]);end[v]|=end[pre[v]=ch[r][j]];
        }
        else ch[u][j]=ch[pre[u]][j];
    }
    int mask;
    for(fr=ta=0,state[0]=ins[0]=0,++ta;fr^ta;){
        u=ins[fr],mask=state[fr];
        if(mask==(1<<n)-1){
            for(;fr;fr=laststate[fr])ans[++id]=lastchar[fr];
            for(i=id;i>=1;--i)putchar('A'+ans[i]);
            return 0;
        }
        for(j=0;j<26;++j)if(!vis[ch[u][j]][mask|end[ch[u][j]]]){
            lastchar[ta]=j,laststate[ta]=fr,ins[ta]=ch[u][j],state[ta]=mask|end[ch[u][j]];
            vis[ins[ta]][state[ta]]=1;
            ta++;
        }++fr;
    }
    return 0;
}