【题目描述】

惠子说：“连环可解也”。
这说明他是一个破解机关的高手，连连环都能解开，鲁班锁什么的自然不在话下。一位
鲁班的后人非常不服气，于是找到惠子，给他出了一道题。
他首先给了惠子一个长度为 n的字符串s和一个长度为 m 的字符串 t，现在，他有 k 个
询问，每个询问是给出两个整数 L,R,询问任选一对(i,j)满足 1≤i≤L,n≥j≥R，删去 s 的
[i+1,j−1]这个区间的子串，剩下两块拼在一起，求t 在其中的匹配数的期望 e。
惠子非常擅长吹逼，但是对数学却搞不太明白，于是他请你来帮他。
为了防止实数的精度误差，你只需要输出 e×L×(n−R+1)

【输入格式】

第一行一个整数 C，表示数据组数
每组数据，第一行是三个整数n，m，k
接下来一行字符串表示 s
接下来一行字符串表示 t
接下里 k 行，每行两个整数 Li,Ri，表示一组询问
C≤5
n≤5×10^4，m≤100，k≤5×10^4
1≤Li＜Ri-1≤n
对于30%的数据，n≤100,k≤100

【输出格式】

对于每组询问，输出一行一个整数表示答案

【样例输入】

1
8 5 4
iamnotsb
iamsb
4 7
3 7
3 8
2 7

【样例输出】

1
1
0
0

【题目分析】

删去一段之后的匹配分两种，一种是本来就匹配的，删除没有影响他，另一种是本来不匹配，删除之后因为两端连接产生的新匹配。

首先考虑第一种：设t的某个匹配为(l,r),推一下公式发现若r≤L，那么这个匹配的贡献为(L−r+1)×(n−R+1)=(L+1)(n−R+1)−r(n−R+1)，那么我们可以预处理一下匹配的r的前缀和匹配数的前缀和,就可以O(1)询问出来了。而若l≥R，那么贡献是(l−R+1)×L，也类似的弄两个前缀和出来就好。

现在考虑因为删除中间一坨而产生的新匹配，我们考虑把t拆开成两个非空部分t1,t2，显然这一种的总贡献等同于t1在[1,L]内的匹配数乘以t2在[R,n]内的匹配数，这个也可以预处理一下前缀和，询问的时候枚举拆开的位置就行了。

【code】

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

const int N = 5e4 + ;

typedef long long ll;

int C, n, m, k, nxt[], revNxt[], lens, lent;

ll pre[N], preCnt[N], last[N], lastCnt[N];

ll tpre[][N], tlast[][N];

char s[N], t[], revt[], revs[N];

inline int read(){

    int i = , f = ; char ch = getchar();

    for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());

    if(ch == '-') f = -, ch = getchar();

    for(; ch >= '' && ch <= ''; ch = getchar())

        i = (i << ) + (i << ) + (ch - '');

    return i * f;

}

inline void wr(ll x){

    if(x < ) putchar('-'), x = -x;

    if(x > ) wr(x / );

    putchar(x %  + '');

}

inline void get_t_nxt(){

    for(int i = , j = ; i <= lent; i++){

        while(j && t[j + ] != t[i]) j = nxt[j];

        if(t[j + ] == t[i]) j++;

        nxt[i] = j;

    }

}

inline void get_r_pre(){

    for(int i = , j = ; i <= lens; i++){

        pre[i] = pre[i - ];

        preCnt[i] = preCnt[i - ];

        while(j && s[i] != t[j + ]) j = nxt[j];

        if(s[i] == t[j + ]) j++;

        if(j == lent){

            pre[i] += i;

            preCnt[i]++;

            j = nxt[j];

        }

    }

}

inline void get_t_rev_nxt(){

    for(int i = , j = ; i <= lent; i++){

        while(j && revt[j + ] != revt[i]) j = revNxt[j];

        if(revt[j + ] == revt[i]) j++;

        revNxt[i] = j;

    }

}

inline void get_l_last(){

    for(int i = , j = ; i <= lens; i++){

        last[i] = last[i - ];

        lastCnt[i] = lastCnt[i - ];

        while(j && revs[i] != revt[j + ]) j = revNxt[j];

        if(revs[i] == revt[j + ]) j++;

        if(j == lent){

            last[i] += n - i + ;

            lastCnt[i]++;

            j = revNxt[j];

        }

    }

}

inline void get_t_pre(){

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

        char now[];

        int now_nxt[] = {};

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

            now[j] = t[j];

        for(int k = , l = ; k <= i; k++){

            while(l && now[l + ] != now[k]) l = now_nxt[l];

            if(now[l + ] == now[k]) l++;

            now_nxt[k] = l;

        }

        for(int k = , l = ; k <= lens; k++){

            tpre[i][k] = tpre[i][k - ];

            while(l && now[l + ] != s[k]) l = now_nxt[l];

            if(now[l + ] == s[k]) l++;

            if(l == i){

                tpre[i][k]++;

                l = now_nxt[l];

            }

        }

    }

}

inline void get_t_last(){

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

        char now[];

        int now_nxt[] = {};

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

            now[j] = revt[j];

        for(int k = , l = ; k <= i; k++){

            while(l && now[l + ] != now[k]) l = now_nxt[l];

            if(now[l + ] == now[k]) l++;

            now_nxt[k] = l;

        }

        for(int k = , l = ; k <= lens; k++){

            tlast[i][k] = tlast[i][k - ];

            while(l && now[l + ] != revs[k]) l = now_nxt[l];

            if(now[l + ] == revs[k]) l++;

            if(l == i){

                tlast[i][k]++;

                l = now_nxt[l];

            }

        }

    }

}

int main(){

    freopen("lianhuan.in","r",stdin);

    freopen("lianhuan.out","w",stdout);

    C = read();

    while(C--){

        n = read(), m = read(), k = read();

        scanf("%s", s + );

        scanf("%s", t + );

        memcpy(revt, t, sizeof t);

        memcpy(revs, s, sizeof s);

        reverse(revt + , revt + m + );

        reverse(revs + , revs + n + );

        lent = m;

        lens = n;

        memset(nxt, , sizeof nxt);

        memset(revNxt, , sizeof revNxt);

        memset(pre, , sizeof pre);

        memset(last, , sizeof last);

        memset(tpre, , sizeof tpre);

        memset(tlast, , sizeof tlast);

        memset(preCnt, , sizeof preCnt);

        memset(lastCnt, , sizeof lastCnt);

        get_t_nxt();

        get_t_rev_nxt();

        get_r_pre();

        get_l_last();

        get_t_pre();

        get_t_last();

        while(k--){

            int L = read(), R = read();

            ll ans = ;

            ans += preCnt[L] * (L + ) * (n - R + );

            ans -= (n - R + ) * pre[L];

            ans -= lastCnt[n - R + ] * (R - ) * L;

            ans += last[n - R + ] * L;

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

                ans += tpre[i][L] * tlast[lent - (i + ) + ][n - R + ];

            wr(ans), putchar('\n');

        }

    }

}

巴特西

【noip模拟】连环

【题目描述】

【输入格式】

【样例输入】

【样例输出】

最新文章

热门文章