【NOI2017模拟6.3】子序列

Description

n,q<=1e5

Solution

遲來的總結

比賽時隻會O(n)Dp離線搞了60分

這個就是F[i]=2*F[i-1]-F[next[i]-1]

其中next[i]表示i前面第一個和i字元相同的位置

正解的Dp長這樣：

設s[i]=c，則F[i][c]=∑F[i-1][k],F[i][k]=F[i-1][k]

然後這樣可以寫成一個轉移矩陣，并且是有逆矩陣的

是以我們可以預處理轉移矩陣的字首積和逆矩陣的倒過來的字首積

那麼詢問直接用這兩個相乘就好了

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=+,mo=+;
int a[][][],b[][][],c[][],d[][],f[],an[];
int n,m,l,r,pre[N][][],suf[N][][];
char st[N];
int read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    int x=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*+ch-'0';
    return x;
}
int mi(int x,int y) {
    int z=;
    for(;y;y/=,x=(ll)x*x%mo)
        if (y&) z=(ll)z*x%mo;
    return z;
}
void get_ni(int x) {
    fo(i,,) b[x][i][i]=;
    fo(i,,) {
        fo(j,i+,)
            if (c[j][i]>c[i][i]) 
                fo(k,i,) {
                    swap(c[j][k],c[i][k]);
                    swap(b[x][j][k],b[x][i][k]);
                }
        int ni=mi(c[i][i],mo-);
        fo(j,i+,) {   
            int t=(ll)c[j][i]*ni%mo;
            fo(k,i,) {
                (c[j][k]+=mo-(ll)c[i][k]*t%mo)%=mo;
                (b[x][j][k]+=mo-(ll)b[x][i][k]*t%mo)%=mo;
            }
        }
    }
    fd(i,,) {
        int ni=mi(c[i][i],mo-);
        fo(j,,i-) {
            int t=(ll)c[j][i]*ni%mo;
            fo(k,i,) {
                (c[j][k]+=mo-(ll)c[i][k]*t%mo)%=mo;
                (b[x][j][k]+=mo-(ll)b[x][i][k]*t%mo)%=mo;
            }
        }
    }
}
int main() {
    freopen("sub.in","r",stdin);
    freopen("sub.out","w",stdout);
    fo(i,,) {
        fo(j,,) {
            a[i][j][j]=;
            a[i][j][i]=;
        }
        memcpy(c,a[i],sizeof(c));
        get_ni(i);
    }
    scanf("%s",st+);n=strlen(st+);
    fo(i,,) pre[][i][i]=suf[][i][i]=;
    fo(w,,n) {
        int x=st[w]-'a';
        memset(d,,sizeof(d));
        fo(k,,)
            fo(i,,)
                fo(j,,)
                    (d[i][j]+=(ll)pre[w-][i][k]*a[x][k][j]%mo)%=mo;
        memcpy(pre[w],d,sizeof(d));

        memset(d,,sizeof(d));
        fo(k,,)
            fo(i,,)
                fo(j,,)
                    (d[i][j]+=(ll)b[x][i][k]*suf[w-][k][j]%mo)%=mo;
        memcpy(suf[w],d,sizeof(d));
    }
    for(m=read();m;m--) {
        l=read();r=read();
        memset(f,,sizeof(f));
        memset(an,,sizeof(an));
        f[]=;
        fo(i,,)
            fo(j,,)
                (an[j]+=(ll)f[i]*suf[l-][i][j]%mo)%=mo;
        memcpy(f,an,sizeof(f));
        memset(an,,sizeof(an));
        fo(i,,)
            fo(j,,)
                (an[j]+=(ll)f[i]*pre[r][i][j]%mo)%=mo;
        int ans=;
        fo(i,,) (ans+=an[i])%=mo;
        printf("%d\n",ans);
    }
}