【JZOJ6216】【20190614】序列计数

深碍√TFBOYSˉ_ 2021-12-23 01:45 175阅读 0赞

## 题目 ##

一个长为\$N\$的串\$S\$，\$M\$询问区间\$\[l,r\]\$不同的子串个数，字符集为$ C $

\$N ,M \\le 10^5 \\ , \\ C \\le 10\$

## 题解 ##

*  这题非常套路。。。
 *  part 1
 *  设\$dp\_\{i,j\}\$为考虑i，字符j结尾的子串个数，考虑\$S\_i=c\$  
    \\\[ \\begin\{align\} &dp\_\{i,j\} = dp\_\{i,j\}\\\\ &dp\_\{i,c\} = \\sum\_\{j\} dp\_\{i-1,j\} + 1 \\end\{align\} \\\]
 *  part 2
 *  设一个大小\$C+1\$的矩阵，写出转移矩阵  
    \\\[ A\_i = \\begin\{pmatrix\} 1 & 0 & 0 & 0\\\\ 0 & 1 & 0 & 0\\\\ 1 & 1 & 1 & 1\\\\ 0 & 0 & 0 & 1\\\\ \\end\{pmatrix\} \\\]  
    它的逆矩阵  
    \\\[ B\_i = \\begin\{pmatrix\} 1 & 0 & 0 & 0\\\\ 0 & 1 & 0 & 0\\\\ -1 & -1 & -1 & -1\\\\ 0 & 0 & 0 & 1\\\\ \\end\{pmatrix\} \\\]  
    只需要预处理出矩阵的前缀即可
 *  part 3
    
    左乘一个A相当于某一行变为所有行的和，可以维护一列的和
    
    右乘一个B相当于其它列减去某一列，可以维护整体减法标记
    
    统计答案也可以直接利用维护的东西，具体见代码
    
    时间复杂度$ O((N+M)C) $

#include<bits/stdc++.h>
    using namespace std;
    const int N=500010,mod=1e9+7;
    int n,m,f1[N][11],f2[N][11];
    
    char s[N],ps[1000000],*pp=ps;
    void flush(){fwrite(ps,1,pp-ps,stdout);pp=ps;}
    void push(char x){if(pp==ps+1000000)flush();*pp++=x;}
    void write(int x){
        static int sta[20],top;
        if(!x){push('0');push('\n');return;}
        while(x)sta[++top]=x%10,x/=10;
        while(top)push(sta[top--]^'0');
        push('\n');
    }
    
    void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}
    void dec(int&x,int y){x-=y;if(x<0)x+=mod;}
    
    struct Mat{
        int c[11][11],s[11],d[11],D;
        void init(){for(int i=0;i<11;++i)c[i][i]=s[i]=1;}
        void plus(int I){
            for(int i=0;i<11;++i){
                int t=c[I][i];c[I][i]=s[i];
                s[i]=(2*s[i]%mod-t+mod)%mod;
            }
        }
        void minus(int I){
            for(int i=0;i<11;++i){
                int t=d[i];d[i]=c[i][I];
                c[i][I]=(2*d[i]%mod-t+mod)%mod;
            }
        }
        void print(int typ){
            for(int i=0;i<11;++i,puts(""))
            for(int j=0;j<11;++j){
                int t=typ?(c[i][j]-d[i]+mod)%mod:c[i][j];
                if(mod-t<t)t=t-mod;
                printf("% 2d ",t);
            }
            puts("\n");
            if(!typ)for(int i=0;i<11;++i)printf("%d ",s[i]);
            puts("\n");
        }
    }A,B;
    
    int main(){
        freopen("sequence.in","r",stdin);
        freopen("sequence.out","w",stdout);
        scanf("%s%d",s+1,&m);n=strlen(s+1);
        A.init(),B.init();f2[0][10]=1;
        for(int i=1;i<=n;++i){
            A.plus(s[i]-'a');
            B.minus(s[i]-'a');
            for(int j=0;j<11;++j){
                f1[i][j]=A.s[j];
                f2[i][j]=(B.c[j][10]-B.d[j]+mod)%mod;
            }
        }
        for(int i=1,l,r,ans;i<=m;++i){
            scanf("%d%d",&l,&r);
            ans=0;for(int j=0;j<11;++j)inc(ans,1ll*f1[r][j]*f2[l-1][j]%mod);
            if(!ans)ans=mod-1;else ans--;write(ans);
        }
        return flush(),0;
    }

转载于:https://www.cnblogs.com/Paul-Guderian/p/11074480.html