比较懒不想分开写了，就都写到这里面吧QAQ
我们首先考虑如何判断一个自动机$A$是否是另一个自动机$t$的升级版。
我们考虑一个二元组$(x,y)$表示走了某个字符串后到达了$A$自动机的$x$号节点，到了$B$自动机的$y$号节点。
那么如果此时$x$是非输出节点而$y$是输出节点，那么说明不成立。否则我们继续遍历他们的后继$(go[x][0],go[y][0])$和$(go[x][1],go[y][1])$。
因为一个二元组是否满足关系只与$(x,y)$有关，与走过怎样的字符串到达该节点无关。所以我们只需要遍历$O(n^2)$个二元组判断即可。
然后我们建出有向图，发现可能会有环。这样求最长链并不好搞，但是因为如果有环的话，那么说明这个环内的所有自动机能产生的串都是一样的。
所以我们可以用tarjan算法把环缩起来作为一个大小为s[x]的点，然后在这张DAG上求最长链。当然也可以用并查集直接将原图缩成DAG。
然后套用经典的DAG上dp的方法求出最长链即可。
首先知道，如果我们有两个自动机$A$和$B$，那么要找出$A$自动机能产生而$B$自动机不能产生的串的个数/最小值这个是可以$O(n^2)$求出来的。
还是利用上面的二元组的方法。之所以能用一个二元组来代表一个状态，因为这之后的转移都是一样的。而与如何到达这个二元组无关。
不妨认为$ans[x][y]$表示到达$(x,y)$的答案，那么当y=0的时候$ans[x][y]=f[x]$,其中$f[x]$表示从x点开始能产生的所有串的数量。
否则$ans[x][y]=\sum_{i=0}^{25}ans[go[x][i]][go[y][i]]$
而考虑如何求$f[x]$。
对于SAM来说，这是个DAG，直接按拓扑序DP即可。
对于子序列组成的自动机。其实很简单，我们每个点x连go[x][i]到距离x最近的i字符的位置。
这样也是个DAG。也可以递推求解。
所以我们把A,B的子串自动机和子序列自动机分别建出来然后dfs即可。复杂度都是$O(n^2)$的
代码大概长这样：
char s[maxn];
struct SAM
{
int last,cnt,go[maxn][26],fa[maxn],l[maxn],f[maxn],c[maxn],sa[maxn];
SAM(){last=cnt=1;}
inline void add(int x)
{
int p=last,np=last=++cnt;l[np]=l[p]+1;
for(;p&&!go[p][x];p=fa[p])go[p][x]=np;
if(!p)fa[np]=1;
else
{
int q=go[p][x];
if(l[q]==l[p]+1)fa[np]=q;
else
{
int nq=++cnt;l[nq]=l[p]+1;
memcpy(go[nq],go[q],sizeof(go[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p&&go[p][x]==q;p=fa[p])go[p][x]=nq;
}
}
}
void build()
{
int n=strlen(s);
for0(i,n-1)add(s[i]-'a');
for1(i,cnt)c[l[i]]++;
for1(i,n)c[i]+=c[i-1];
for1(i,cnt)sa[c[l[i]]--]=i;
for1(i,cnt)f[i]=1;
for3(i,cnt,1)for0(j,25)(f[sa[i]]+=f[go[sa[i]][j]])%=mod;
}
}A,C;
bool v[maxn][maxn];
int ans[maxn][maxn];
struct QAQ
{
int v[26],go[maxn][26],f[maxn];
inline void build()
{
int n=strlen(s);
for3(i,n+1,1)
{
for0(j,25)go[i][j]=v[j];
if(i==1)continue;
v[s[i-2]-'a']=i;
}
for1(i,n+1)f[i]=1;
for3(i,n+1,1)for0(j,25)(f[i]+=f[go[i][j]])%=mod;
}
}B,D;
inline int dfs1(int x,int y)
{
if(x&&!y)return A.f[x];
if(v[x][y])return ans[x][y];
v[x][y]=1;ans[x][y]=0;
for0(i,25)(ans[x][y]+=dfs1(A.go[x][i],C.go[y][i]))%=mod;
return ans[x][y];
}
inline int dfs2(int x,int y)
{
if(x&&!y)return A.f[x];
if(v[x][y])return ans[x][y];
v[x][y]=1;ans[x][y]=0;
for0(i,25)(ans[x][y]+=dfs2(A.go[x][i],D.go[y][i]))%=mod;
return ans[x][y];
}
inline int dfs3(int x,int y)
{
if(x&&!y)return B.f[x];
if(v[x][y])return ans[x][y];
v[x][y]=1;ans[x][y]=0;
for0(i,25)(ans[x][y]+=dfs3(B.go[x][i],C.go[y][i]))%=mod;
return ans[x][y];
}
inline int dfs4(int x,int y)
{
if(x&&!y)return B.f[x];
if(v[x][y])return ans[x][y];
v[x][y]=1;ans[x][y]=0;
for0(i,25)(ans[x][y]+=dfs4(B.go[x][i],D.go[y][i]))%=mod;
return ans[x][y];
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%s",s);A.build();B.build();
scanf("%s",s);C.build();D.build();
memset(v,0,sizeof(v));
printf("%d\n",dfs1(1,1));
memset(v,0,sizeof(v));
printf("%d\n",dfs2(1,1));
memset(v,0,sizeof(v));
printf("%d\n",dfs3(1,1));
memset(v,0,sizeof(v));
printf("%d\n",dfs4(1,1));
return 0;
}
这题其实和上一题差不多，我们令$ans[x][y]$表示从初始点到达二元组$(x,y)$走的字符串的最短长度。
那么我们就可以按拓扑序bfs+DP了。
值得一提的是，这四个子问题也都是可以直接用DP解决的。
而仔细一想又会发现这两种做法其实是一样的。
可以参见：jiry_2
先考虑一下比较容易想到的dp。令$dp[i][j][k]$表示前i个字符，最长同色长度为j，然后最后一个字符是k。那么这个概率可以通过枚举k字符的长度来得到。
具体来说有$$\begin{aligned}dp[i][j][k]=&\sum_{l=i-j}^{i-1}\sum_{p!=k}dp[l][j][p]*g[l+1][i][k]\\&+\sum_{p!=k}dp[i-j][j-1][p]*g[i-j+1][i][k]\end{aligned}$$
其中g[i][j][k]表示i-j全为k颜色的概率，这个显然可以$O(n^2m)$预处理出来。
然后直接这样做是$O(n^3m^2)$的，可以拿到$60$分。
如果状态表达式还是这样的话，并不容易优化。
我们考虑用$dp[i][j][k]$表示前i个字符，最长同色长度<=j,最后一个字符是k。那么可以去掉后面那个单独的一项。这样状态转移方程是这样的
$$dp[i][j][k]=\sum_{l=i-j}^{i-1}\sum_{p!=k}dp[l][j][p]*g[l+1][i][k]$$
还有不同的地方就是初值的变化。
然后继续优化，因为状态数是$O(n^2m）$的。所以内层不支持我们枚举$l$，顶多枚举一个$p$。
考虑将l这一维搞成前缀和，但与之带来的问题就是每个dp值乘的东西是不一样的。
但是我们可以搞搞搞！我们让它乘的东西一样。也就是说我们直接维护
$$f[i][j][k]=\sum_{l=0}^{i}dp[l][j][k]*g[l+1][i][k]$$
这样要得出一个前缀dp值的贡献就直接乘以一个相同的数就好了。也就是把不一样的补齐到一块儿。
复杂度$O(n^2m^2)$，亲测可过。。。
代码大概长这样：
int n,m;
double p[maxn][maxm],f[maxn][maxn][maxm],g[maxn][maxn][maxm];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();
for1(i,n)for1(j,m)scanf("%lf",&p[i][j]);
for1(k,m)for1(i,n)
{
g[i][i][k]=p[i][k];
for2(j,i+1,n)g[i][j][k]=g[i][j-1][k]*p[j][k];
}
for1(i,n)f[0][i][0]=1.0;
for1(i,n)for1(j,n)for0(k,m)
{
for0(l,m)if(l!=k)f[i][j][k]+=f[i-1][j][l]*g[i][i][k]-(i-j-1>=0?f[i-j-1][j][l]*g[i-j][i][k]:0);
f[i][j][k]+=f[i-1][j][k]*g[i][i][k];
}
double ans=0.0;
for1(i,n)for1(j,m)ans+=(f[n][i][j]-f[n][i-1][j])*i;
printf("%.6f\n",ans);
return 0;
}
UPD：这题还有一种复杂度更低以及思考难度更低的做法。
我们令$$s[i][j]=\sum_{k=1}^{m}dp[i][j][k]$$
我们不再限制上一个的结尾与该结尾颜色不同，我们用全部的概率减去长度一定超过j的概率就好了。
那么$$dp[i][j][k]=s[i-1][j]*g[i][i][k]\\-(s[i-j-1][j]-dp[i-j-1][j][k])*g[i-j][i][k]$$
我们来看看这个公式是怎么得到的。
首先如果令$dp[i][j][k]=s[i-1][j]*g[i][i][k]$$的话出现的不合法的情况只有可能是产生了连续的j+1个k颜色的。
而且位置是从i-j到i。
这样我们需要把这个概率减掉。这个概率是就是i-j-1位置不是k的最长同色<=j的概率*g[i-j][i][k]
这样我们就得到了一个复杂度为$O(n^2m)$的优秀算法。
n个点的带权树，要求从n个点中选出k个点，使得这k个点两两之间的距离最小。n<=2000 k<=50
其实是个傻逼题。
把状态$dp[i][j]$的含义设为在i子树中选择j个点，并且这j个点两两之间的距离+这j个点到i的距离之和最小是多少。
然后就直接树形背包辣
评论 (0)
