LOJ #6074. 「2017 山东一轮集训 Day6」子序列

时间：2023-03-08 23:17:55
LOJ #6074. 「2017 山东一轮集训 Day6」子序列

#6074. 「2017 山东一轮集训 Day6」子序列

分析：

　　首先设f[i][j]为到第i个点，结尾字符是j的方案数，这个j一定是从i往前走，第一个出现的j，因为这个j可以代替掉前面所有j。于是有转移方程：

$$ f_{i,j}= \begin{cases} f_{i-1,j}&,j\neq S_i\\ \sum_{k=1}^{m+1}f_{i-1,k}&,j=S_i \end{cases} $$

　　表示如果当前j不是s[i]的话，最靠后的结尾的j还是那个位置，从i-1转移即可，否则，最靠后的s[i]变成i这个位置，于是加上前面所有最靠后出现的字符即可（即从i往前走到k，如果s[k]在k+1~i之间没有s[k]了，就加上）。

　　这个dp还有一个形象的解释：每个i向它后面第一个出现的字符连有向边（即如果i->j有边，那么i+1~j之间没有s[[j]），然后DAG上的路径数就是答案。

　　然后可以对每个位置求一个$10 \times 10$的转移矩阵$A_i$，$F_i$是一个$10 \times 1$的矩阵，有$F_i = A_i \times F_{i - 1}$。

　　于是可以分别维护矩阵的前缀积，和逆矩阵的前缀积。

　　然后复杂度可以做到$nc^3+qc^2$，由于这个矩阵的性质，可以$nc^2$预处理，所以可以做到$nc^2+qc^2$，至于如何做到$nc+qc$，可以看这。

代码：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#include<bitset>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , mod = 1e9 + ;

struct Matrix{ int a[][]; Matrix() { memset(a, , sizeof(a)); } } s1[N], s2[N];

char str[N];

int s[N], tmp[];

inline void add(int &x,int y) { x += y; if (x >= mod) x -= mod; }

inline void sub(int &x,int y) { x -= y; if (x < ) x += mod; }

void init(int n) {

    for (int i = ; i < ; ++i) s1[].a[i][i] = s2[].a[i][i] = ;

    for (int i = ; i < ; ++i) s1[].a[i][i] = ;

    for (int i = ; i < ; ++i) s1[].a[s[]][i] = ;

    for (int i = ; i <= n; ++i) {

        s1[i] = s1[i - ];

        for (int j = ; j < ; ++j) tmp[j] = ;

        for (int j = ; j < ; ++j)

            for (int k = ; k < ; ++k) add(tmp[j], s1[i - ].a[k][j]);

        for (int j = ; j < ; ++j) s1[i].a[s[i]][j] = tmp[j];

    }

    for (int i = ; i < ; ++i) s2[].a[s[]][i] = mod - ;

    for (int i = ; i < ; ++i) s2[].a[i][i] = ;

    for (int i = ; i <= n; ++i) {

        s2[i] = s2[i - ];

        for (int j = ; j < ; ++j) for (int k = ; k < ; ++k) if (k != s[i]) sub(s2[i].a[j][k], s2[i - ].a[j][s[i]]);

    }

}

int main() {

    scanf("%s", str + );

    int n = strlen(str + );

    for (int i = ; i <= n; ++i) s[i] = str[i] - 'a';

    init(n);

    for (int m = read(); m --; ) {

        int l = read(), r = read();

        for (int i = ; i < ; ++i) tmp[i] = ;

        for (int i = ; i < ; ++i) add(tmp[i], s2[l - ].a[i][]);

        int sum = ;

        for (int i = ; i < ; ++i)

            for (int j = ; j < ; ++j)

                add(sum, 1ll * s1[r].a[i][j] * tmp[j] % mod);

        cout << (sum -  + mod) % mod << "\n";

     }

    return ;

}

相关文章