LOJ.6074.[2017山东一轮集训Day6]子序列(DP 矩阵乘法)

题目链接


参考yww的题解。本来不想写来但是他有一些笔误...而且有些地方不太一样就写篇好了。
不知不觉怎么写了这么多...


\(60\)分的\(O(n^2)\)做法就是,令\(f[i]\)表示以\(s[i]\)结尾的不同子序列个数,\(las[c]\)表示\(c\)字符上次出现的位置(没有出现过则为\(-1\)),转移是:\[f[i]=\begin{cases}2f[i-1]+1&,las[s[i]]=-1\\2f[i-1]-f[las[s[i]]]&,las[s[i]]\neq-1\end{cases}\]


上面这个做法挺妙的,但是好像没什么优化空间。
考虑另一种DP,令\(f[i][j]\)表示前\(i\)个字符,以字符\(j\)结尾的不同子序列个数。转移为:\[f[i][j]=\begin{cases}f[i-1][j-1]&,j\neq s_i\\\sum_{k=0}^mf[i-1][k]&,j=s_i\end{cases}\]

其中字符集是\(0\sim m-1\)(\(m=9\)),特别的令\(f[i][m]\)表示前\(i\)个字符什么也没选的方案数,因为子序列可以从任意位置开始。
这样不会算重,感觉也挺妙的。。(好吧是自己菜)

显然可以用矩阵把转移表示出来。令\[F_i=\left[\begin{matrix}f_{i,1}\\f_{i,2}\\\vdots\\f_{i,m+1}\end{matrix}\right]\]

转移矩阵就是\(A[i][i]=1,A[c][j]=1\ (c=s[i])\)(把单位矩阵\(s[i]\)那一行全设为\(1\))。就是这样子:\[F_i=A_iF_{i-1}\\A_i=\left[\begin{matrix}1&&&&\\&1&&&\\1&1&1&1&1\\&&&1&\\&&&&1\end{matrix}\right]\]

再考虑一下初始化、最后的求和,令\[\begin{aligned}U&=\left[\begin{matrix}1\\1\\\vdots\\1\end{matrix}\right]\\V&=\left[\begin{matrix}0\ 0\ \cdots\ 0\ 1\end{matrix}\right]\end{aligned}\]

\(A_i\)显然有逆矩阵(可以比较容易地写出来)。那么区间\([l,r]\)的答案就是\[\begin{aligned}&UA_rA_{r-1}\cdots A_lV\\=&UA_rA_{r-1}\cdots A_1{A_1}^{-1}{A_2}^{-1}\ldots A_{l-1}V\end{aligned}\]

这里把\(U\)放到了前面,\(V\)放到了后面,都一样,我觉得还是这样方便一些...
需要注意矩阵乘法没有交换律,注意乘的顺序。
所以预处理一个转移矩阵的前缀积\(f_i\)、转移矩阵逆元的前缀积\(g_i\),就可以\(O(m^3)\)回答一次询问了。
预处理\(f_i\)的时候让它和\(U\)乘一下,同理\(g_i\)和\(V\)乘一下,询问就是\(O(m)\)的了。

但是预处理的复杂度还是\(O(nm^3)\)的(但是开O2已经能过了...)。
注意到转移矩阵非常特殊,一个矩阵\(M\)乘上\(A_i\)时,\(M_{s_i,j}'\)是\(A_i\)第\(j\)列元素的和,\(M'\)其它行的元素不变。这样乘\(A_i\)可以做到\(O(m)\)。
同时左乘\(U\)得到的矩阵就是对列求和。
那么我们维护\(f_i\)的时候(乘了\(U\),是个\(1\times n\)的),第\(j\)列的和即\(f_{i,j}\),就是上一次第\(j\)列的和\(*2\)减去\(A_{s_i,j}\),上一次第\(j\)列的和就是\(f_{i-1,j}\)。那么这个转移也是\(O(m)\)的。

同理,\(A_i^{-1}\)大概是这样:\[A_i=\left[\begin{matrix}1&&&&\\&1&&&\\-1&-1&1&-1&-1\\&&&1&\\&&&&1\end{matrix}\right]\]

即\(A[i][i]=1,A[c][j]=-1\ (c=s[i],j\neq i)\)(把单位矩阵\(s[i]\)那一行除了\(A_{s[i],s[i]}\)全设为\(-1\))。
一个矩阵乘\(A_i^{-1}\)时,除了\(c=s[i]\)列之外的列\(M_{i,j}\),都会减去\(M_{i,c}\),第\(c\)列的元素不变。维护一个整行减了多少的标记,对\(M_{i,c}\)单点修改一下即可。
注意到假设其中一行是:\(\left[a_1-v\quad a_2-v\quad a_3-v\quad a_4-v\right]\),\(s[i]=3\)时,会变成\(\left[a_1-a_3\quad a_2-a_3\quad (2a_3-v)-a_3\quad a_4-a_3\right]\),也就是对\(3\)单独修改一下,所有数每次会减掉上次那个数,打个标记修改也是\(O(m)\)的了。

维护\(g_i\)时,注意到右乘一个\(V\)就是把矩阵最后一列取出来,直接求即可。同样\(O(m)\)。

那么总复杂度就做到\(O((n+q)m)\)啦。


//263ms 8760K
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define rg register
#define mod 1000000007
#define Mod(x) x>=mod&&(x-=mod)
#define Add(x,v) (x+=v)>=mod&&(x-=mod)
#define Add2(x,y) (x+y>=mod?x+y-mod:x+y)
//#define gc() getchar()
#define MAXIN 500000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+7,M=10;
const LL LIM=6e18;

int s[N],f[N][M],g[N][M];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-48,c=gc());
    return now;
}
void Pre(const int n)
{
    static int A[M][M],B[M][M],tag[M];
    for(int i=0; i<M; ++i) A[i][i]=B[i][i]=f[0][i]=1;
    g[0][M-1]=1;
    for(rg int i=1; i<=n; ++i)
    {
        rg int c=s[i];
        for(rg int j=0; j<M; ++j)
        {
            rg int tmp=f[i-1][j]<<1; Mod(tmp);
            f[i][j]=Add2(tmp,mod-A[c][j]);
            A[c][j]=f[i-1][j];
            tmp=B[j][c]<<1, Mod(tmp); rg int tmp2=B[j][c];
            g[i][j]=Add2(B[j][M-1],mod-B[j][c]);
            B[j][c]=Add2(tmp,mod-tag[j]), tag[j]=tmp2;
        }
    }
}

int main()
{
    int n=0;
    register char c; while(isalpha(c=gc())) s[++n]=c-'a';
    Pre(n);
    for(int q=read(); q--; )
    {
        int l=read()-1,r=read();
        LL ans=0;
        if(l) for(int i=0; i<M; ++i) ans+=1ll*f[r][i]*g[l][i], ans>=LIM&&(ans%=mod);
        else ans=f[r][M-1];
        printf("%lld\n",(ans-1)%mod);
    }

    return 0;
}
上一篇:DAY6 元组、字典与集合


下一篇:loj#6074. 「2017 山东一轮集训 Day6」子序列(矩阵乘法 dp)