异位坍缩题解

littleKtian · 2021-02-18 18:13:33 · 题解

样例解释已经很明显告诉你先计算所有选择子串方案的概率和再除掉方案数了。

先考虑去掉 l 和 r 的限制的情况下如何计算。

设 f_{i,0/1} 表示所有以 i 为结尾的子串，选择相应的 b，满足 b 对于相应子串是「忠诚的」，且 b 的结尾与相应子串相同/不同的概率和。

有递推式 \begin{cases}f_{i,0}=\dfrac{1}{2}(f_{i-1,0}+f_{i-1,1}+1),f_{i,1}=\dfrac{1}{2}(f_{i-1,0}+1)&a_i=0\\f_{i,0}=\dfrac{1}{2}(f_{i-1,0}+f_{i-1,1}+1),f_{i,1}=\dfrac{1}{2}(f_{i-1,1}+1)&a_i=1\end{cases}。

或者写成 f_{i,0}=\dfrac{1}{2}(f_{i-1,0}+f_{i-1,1})+\dfrac{1}{2},f_{i,1}=\dfrac{1}{2}(f_{i-1,a_i})+\dfrac{1}{2}。

特别的，f_{0,0}=f_{0,1}=0。

观察如何给这个式子加上 l 和 r 的限制。

注意到式子中的 +\dfrac{1}{2} 其实就类似于 l=1 时产生的限制，这提示我们可以在 dp 时保留保留式子其他部分，将 +\dfrac{1}{2} 根据 l 的限制进行更换，同时再根据 r 的限制再在原式中减去一部分。

因此我们修改 f 的定义。设 f_{i,0/1} 表示所有以 i 为结尾的且长度在 l 到 r 之间的子串，选择相应的 b，满足 b 对于相应子串是「忠诚的」，且 b 的结尾与相应子串相同/不同的概率和，另外设 fl_{i,0/1},fr_{i,0/1} 分别表示以 i 为结尾的长度为 l /为 r+1 的子串，有多少个 01 串 b 使得 b 对其是「忠诚的」，且b 的结尾与其相同/不同（如果 i< l / i< r+1，那么 fl_{i,0}=fl_{i,1}=0 / fr_{i,0}=fr_{i,1}=0）。

于是有 f_{i,0}=\dfrac{1}{2}(f_{i-1,0}+f_{i-1,1})+\dfrac{fl_{i,0}}{2^l}-\dfrac{fr_{i,0}}{2^{r+1}},f_{i,1}=\dfrac{1}{2}(f_{i-1,a_i})+\dfrac{fl_{i,1}}{2^l}-\dfrac{fr_{i,1}}{2^{r+1}}。

现在的问题是如何计算 fl 和 fr。

（因为两者计算方法基本相同所以下面只讲一个）

假设我们现在要计算一个串有多少个串 b 对其是「忠诚的」，设 g_{i,0/1} 表示到第 i 个位置为止有多少个串对其是「忠诚的」。

有递推式 g_{i,0}=g_{i-1,0}+g_{i-1,1},g_{i,1}=g_{i-1,a_i}。特别的，g_{1,0}=g_{1,1}=1。

把递推式写成矩阵的形式，有：

\begin{cases}\begin{bmatrix}g_{i-1,0}&g_{i-1,1}\end{bmatrix}\begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}g_{i,0}&g_{i,1}\end{bmatrix}&a_i=0\\\begin{bmatrix}g_{i-1,0}&g_{i-1,1}\end{bmatrix}\begin{bmatrix}1&0\\1&1\end{bmatrix}=\begin{bmatrix}g_{i,0}&g_{i,1}\end{bmatrix}&a_i=1\end{cases}

因为两种情况使用的矩阵不同，我们不能直接进行矩阵快速幂。但我们发现在计算时用的都是一连串的矩阵，，并且头部和尾部都往一个方向移动。所以我们可以在计算时直接在尾部乘上一个新的矩阵，并在头部乘上一个逆矩阵，这样每次只需要做两次矩阵乘法就能直接得到新的用于计算的矩阵。从而计算出 fl 和 fr。

上面两个矩阵的逆矩阵分别为 \begin{bmatrix}0&1\\1&-1\end{bmatrix} 和 \begin{bmatrix}1&0\\-1&1\end{bmatrix}。

时间复杂度 O(n)。

#include<bits/stdc++.h>
#define p 998244353
using namespace std;
struct jx{
    int a[2][2];
};
jx operator *(const jx &x,const jx &y)
{
    jx z;
    z.a[0][0]=(1ll*x.a[0][0]*y.a[0][0]+1ll*x.a[0][1]*y.a[1][0])%p;
    z.a[1][0]=(1ll*x.a[1][0]*y.a[0][0]+1ll*x.a[1][1]*y.a[1][0])%p;
    z.a[0][1]=(1ll*x.a[0][0]*y.a[0][1]+1ll*x.a[0][1]*y.a[1][1])%p;
    z.a[1][1]=(1ll*x.a[1][0]*y.a[0][1]+1ll*x.a[1][1]*y.a[1][1])%p;
    return z;
}
jx A[2],B[2],aa;
int n,l,r,a[5000005],fl[2][5000005],fr[2][5000005],f[2][5000005],ans,cho,pl,pr,p2;
int P(int x,int y=p-2)
{
    int z=1;
    for(;y;x=1ll*x*x%p,y>>=1)if(y&1)z=1ll*z*x%p;
    return z;
}
int main()
{
    A[0].a[0][0]=A[0].a[0][1]=A[0].a[1][0]=1,B[0].a[0][1]=B[0].a[1][0]=1,B[0].a[1][1]=p-1;
    A[1].a[0][0]=A[1].a[1][0]=A[1].a[1][1]=1,B[1].a[0][0]=B[1].a[1][1]=1,B[1].a[1][0]=p-1;
    scanf("%d%d%d",&n,&l,&r);
    pl=P(P(2,l)),pr=P(P(2,r+1)),cho=P((1ll*(n*2-l-r+2)*(r-l+1)/2)%p),p2=P(2);
    for(int i=1;i<=n;i++)
    {
        char ch=getchar();
        while(ch!='0'&&ch!='1')ch=getchar();
        a[i]=ch-'0';
    }
    aa.a[0][0]=aa.a[1][1]=1,aa.a[0][1]=aa.a[1][0]=0;
    for(int i=1;i<l;i++)aa=aa*A[a[i]];
    for(int i=l;i<=n;i++)
    {
        aa=B[a[i-l+1]]*aa*A[a[i]];
        fl[0][i]=(aa.a[0][0]+aa.a[1][0])%p,fl[1][i]=(aa.a[0][1]+aa.a[1][1])%p;
    }
    aa.a[0][0]=aa.a[1][1]=1,aa.a[0][1]=aa.a[1][0]=0;
    for(int i=1;i<=r;i++)aa=aa*A[a[i]];
    for(int i=r+1;i<=n;i++)
    {
        aa=B[a[i-r]]*aa*A[a[i]];
        fr[0][i]=(aa.a[0][0]+aa.a[1][0])%p,fr[1][i]=(aa.a[0][1]+aa.a[1][1])%p;
    }
    for(int i=1;i<=n;i++)f[0][i]=((1ll*p2*(f[0][i-1]+f[1][i-1])+1ll*pl*fl[0][i]-1ll*pr*fr[0][i])%p+p)%p,f[1][i]=((1ll*p2*f[a[i]][i-1]+1ll*pl*fl[1][i]-1ll*pr*fr[1][i])%p+p)%p;
    for(int i=1;i<=n;i++)ans=(ans+(f[0][i]+f[1][i])%p)%p;
    printf("%lld",1ll*ans*cho%p);
}

异位坍缩 题解

异位坍缩题解