JZM 的印象笔记（卷积，分块）

阅读原文时间：2023年07月10日阅读：1

题面

题目背景

大名鼎鼎的 OI 天花板选手 JZM 对自己的好伙伴——印象笔记有些生疏了

题目描述

作为一名 OI 选手，他的笔记中的字母只包含数字0和1。
JZM 在印象笔记中找到了一行

N 个字母的印象语录，而 JZM 打算朗读一段长度为

M 的话语。由于 JZM 记得不是很清楚，他需要从印象语录的某一个位置开始，对照着印象语录进行朗读。当印象语录上的当前字符和 JZM 话语中即将朗读的字符不一样时，JZM 就会跳过这对不一样的字符继续朗读下一个位置，我们称之为发生一次停顿。JZM 所要朗读的话语有些段落文辞优美，有些段落儒雅随和。具体地，该话语中第

i 个字符有优美度

f_i

fi，如果在第

i 个字符上发生停顿，JZM 的容忍度就会减少

f_i

fi 。JZM 的初始容忍度为

K，当他的容忍度降至 0 以下时，JZM 就不想继续朗读了。

例如，印象语录为 1101110，而 JZM 则打算从第 3 个字符开始对照，朗读 110011，

K=1

K=1，

{

}

f=\{1,1,4,5,1,3\}

f={1,1,4,5,1,3} 。

过程中，印象语录的第三个字符 0 与 JZM 所要朗读的第一字符 1 不同，于是他发生了一次停顿，容忍度减少 1 。

之后，语录中的第四个字符 1 和话语的第二个字符 1 相同，顺利朗读，进入下一对。

印象语录的第五个字符 1 与 JZM 所要朗读的第三个字符 0 不同，于是他又发生了一次停顿，容忍度减少 4，变为 -4，于是 JZM 停下了朗读。

我们把 JZM 停下朗读时当前进行到印象语录中字符的位置称为终止位置，上面这个例子中， JZM 的终止位置为 5 。特别地，假如 JZM 从第

i 个位置开始顺利朗读完了

M 个字符，他的终止位置是

i+M

i+M；假如读到一半印象语录结束了，他的终止位置是

N+1

N+1 。

JZM 此时要断章取义，他想尽可能顺利地朗读话语，于是身为 OI 领头羊的他把这个小任务交了你，希望你能告诉他，对于每一个可能的朗读起始位置 1 到 N ，他的终止位置会是哪里。

输入格式

第一行三个整数

N\;M\;K

NMK 表示印象语录的长度，JZM 朗读话语的长度和 JZM 的容忍度。
第二行

N 个

0/1

0/1 字符，为印象语录。
第三行

M 个

0/1

0/1 字符，为 JZM 朗读的话语。
第三行

M 个整数，为话语中每一个字符的优美度。

输出格式

输出一行

N 个整数，第

i 个整数表示对于朗读起始位置

i ，JZM 的终止位置会是哪里。

Sample Input

20 10 15
10011111001101010110
1011110101
2 1 4 7 4 8 3 6 4 7

Sample Output

11 12 13 13 11 13 17 15 19 15 20 18 20 21 21 21 21 21 21 21

数据范围

对于测试点1:

≤

N,M \leq 10^3

N,M≤103
对于测试点2~3:

K=0

K=0
对于测试点4 :

≤

100

K\leq 100

K≤100
对于测试点5~6：话语中所有字符均为 1
对于测试点7~10 : 无特殊限制
对于所有的数据，

≤

1\leq N,M\leq 10^5\;,\;0\leq K\leq 10^8\;,\;1\leq f_i\leq10^3

1≤N,M≤105,0≤K≤108,1≤fi≤103
时间限制 2 s，空间限制 64 MB。

题解

考试中，我正敲着 K ≤ 100 的部分分，调试着后缀数组+ RMQ 的百行大代码，忽然听见对面的大佬们在小声讨论：

\;\;\;\;

“你用的是 FFT 还是 NTT ？我觉得 FFT 可能有点慢。”
NTT ？哪一到题？T1 跟 NTT 有什么关系？

\;\;\;\;

“你开的块大小是多少？我开了 3000”
分块？・∀・？怎么又跟分块扯上关系了？
罢了罢了，肯定不是这道题。
于是我就打了前面四个点的暴力，相比起他们的 AC，我只拿了 50 pts（多了十分？看下文）

如果限定终止位置在哪里，我们就可以想想怎么快速地算容忍度会降多少，是否降到 0 以下。
设话语为 S 字符串，印象语录为 T 字符串，

ans_i

ansi 代表第

i 个位置开始匹配完整个字符串 S 后消耗的容忍度，则：

∑

(

[

−

]

[

]

)

⋅

ans_i=\sum_{j=1}^{m}(S[i+j-1]\,xor\,T[j])\cdot f_j

ansi=j=1∑m(S[i+j−1]xorT[j])⋅fj

这是笔者进行的基础的题面翻译，大佬们是怎么跟 NTT 扯上关系的呢？

我们想，异或的本质是同 0 异 1，互异的情况只有 0,1 和 1,0 （这不废话）

于是考虑这两种情况算贡献，顺便把

−

i+j-1

i+j−1 变成

(

−

)

k\;,(k-j=i-1)

k,(k−j=i−1)：

∑

−

(

[

]

[

]

[

]

[

]

)

ans_i=\sum_{k-j=i-1}f_j([S_k=1][T_j=0] + [S_k=0][T_j=1])

ansi=k−j=i−1∑fj([Sk=1][Tj=0]+[Sk=0][Tj=1])

其中的

[

]

[S_k=1]

[Sk=1] 是个条件表达式，

S_k=1

Sk=1 则值为 1，否则为 0，或许这样还是不太明显，我们再变：

∑

−

[

]

⋅

(

[

]

)

∑

−

[

]

⋅

(

[

]

)

ans_i=\sum_{k-j=i-1}[S_k=1]\cdot (f_j[T_j=0]) + \sum_{k-j=i-1}[S_k=0]\cdot (f_j[T_j=1])

ansi=k−j=i−1∑[Sk=1]⋅(fj[Tj=0])+k−j=i−1∑[Sk=0]⋅(fj[Tj=1])

两个卷积！（只需把数组倒一倒）这该是多么强的直觉才能发现是卷积啊

所以我们就可以在

(

)

log

⁡

(N+M)\log N

(N+M)logN 的时间求出从每个位置开始、匹配完整条话语的容忍度下降值。

那怎么想到分块的呢？

同样地，我们可以在

(

)

log

⁡

(N+B)\log N

(N+B)logN 的时间求出从每个位置开始、匹配完话语中一段长为

B 的块的容忍度下降值。

那么考虑将 S 分

\frac{M}{B}

BM 个为大小为

B 的块，从前到后 NTT 计算每个块的卷积，假如某个位置已经不能再匹配完这个块（容忍度在这个块降到 0 以下），则

(

)

O(B)

O(B) 地算出它在哪里终止。

大概复杂度在

(

⋅

log

⁡

⋅

)

O(N\cdot\frac{M}{B}\log N+N\cdot B)

O(N⋅BMlogN+N⋅B) 左右，因此理论上

log

⁡

B=\sqrt{N\log N}

B=NlogN

最优，考虑暴力常数小，我们就取

(

)

B=max(\frac{M}{30},1)

B=max(30M,1) 就行了，最后还得卡卡常。

CODE（正解）

#include<set>
#include<map>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define DB double
#define LL long long
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
    while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
    return f * x;
}
const int MOD = 998244353;
int n,m,i,j,s,o,k,B;
int f[MAXN];
char ss[MAXN],s1[MAXN],s2[MAXN<<1];
int QM(int x) {return x>=MOD ? (x-MOD) : x;}
int qkpow(int a,int b) {
    int res = 1;
    while(b > 0) {
        if(b & 1) res = res *1ll* a % MOD;
        a = a *1ll* a % MOD;b >>= 1;
    }return res;
}
int xm[MAXN<<2],rev[MAXN<<2],om;
void NTT(int *s,int n,int op) {
    for(int i = 1;i < n;i ++) {
        rev[i] = ((rev[i>>1]>>1) | ((i & 1) ? (n>>1):0));
        if(rev[i] < i) swap(s[rev[i]],s[i]);
    }
    om = qkpow(3,(MOD-1)/n); xm[0] = 1;
    if(op < 0) om = qkpow(om,MOD-2);
    for(int i = 1;i <= n;i ++) xm[i] = xm[i-1] *1ll* om % MOD;
    for(int k = 2,t=(n>>1);k <= n;k<<=1,t>>=1) {
        for(int j = 0;j < n;j += k) {
            for(int i = j,l = 0;i < j+(k>>1);i ++,l += t) {
                int A = s[i],B = s[i+(k>>1)];
                s[i] = (A + B *1ll* xm[l] % MOD) % MOD;
                s[i+(k>>1)] = (A +MOD- B *1ll* xm[l] % MOD) % MOD;
            }
        }
    }
    if(op < 0) {
        int invn = qkpow(n,MOD-2);
        for(int i = 0;i < n;i ++) s[i] = s[i] *1ll* invn % MOD;
    }return ;
}
int kk[MAXN],rl[MAXN];
int aa[MAXN<<2],bb[MAXN<<2];
int C[MAXN<<2],D[MAXN<<2];
int rpos(int pos,int st,int kk) {
    for(int j = st;j <= m && pos <= n;j ++) {
        if(ss[pos] != s1[j]) kk -= f[j];
        if(kk < 0) break;
        pos ++;
    }
    return pos;
}
int main() {
    freopen("mata.in","r",stdin);
    freopen("mata.out","w",stdout);
    n = read(); m = read(); k = read();
    B = max(1,m/30);
    scanf("%s",ss + 1);
    scanf("%s",s1 + 1);
    LL sm = 0;
    for(int i = 1;i <= m;i ++) f[i] = read(),sm += f[i];
    if(k >= sm) {
        for(int i = 1;i <= n;i ++) {
            printf("%d ",min(n+1,i+m));
        }ENDL;
        return 0;
    }
    int le = 1; while(le <= n+B) le <<= 1;
    for(int i = 1;i <= n;i ++) {
        kk[i] = k;
        aa[i] = (ss[n-i+1] == '1' ? 1:0);
        bb[i] = aa[i] ^ 1;
    }
    NTT(aa,le,1); NTT(bb,le,1);
    for(int i = 1;i <= m;i += B) {
        int rr = min(i+B-1,m);
        for(int j = 0;j <= le;j ++) C[j]=D[j]=0;
        for(int j = 1,j2 = i;j2 <= rr;j2 ++,j ++) {
            C[j] = (s1[j2] == '1' ? f[j2]:0);
            D[j] = f[j2] - C[j];
        }
        NTT(C,le,1);NTT(D,le,1);
        for(int j = 0;j < le;j ++) C[j] = C[j] *1ll* bb[j] % MOD,D[j] = D[j] *1ll* aa[j] % MOD;
        NTT(C,le,-1);NTT(D,le,-1);
        for(int j = 1;j <= n+1-i;j ++) {
            int ad = n-j+3-i;
            if(!rl[j]) {
                if(kk[j] - C[ad] - D[ad] < 0) {
                    rl[j] = rpos(j+i-1,i,kk[j]);
                }
                kk[j] -= C[ad]+D[ad];
            }
        }
    }
    for(int i = 1;i <= n;i ++) {
        if(kk[i] >= 0) rl[i] = min(n+1,i+m);
        printf("%d ",rl[i]);
    }ENDL;
    return 0;
}

彩蛋

为什么我会得 50 pts 呢？我看了下结果，有 40 的有 60 的，就我和一个正解打爆的人得了 50 。

我过了最后一个点，0.2 s，正解跑 1.5 s。

这是因为我特判了一种情况：当

≥

∑

K\geq \sum f_i

K≥∑fi 时，每个位置都可以随便匹配，因此对于位置

i 只用输出

min

⁡

(

)

\min(i+M,N+1)

min(i+M,N+1) ，如果是暴力的话，这个点可以卡掉那些认为 K 很小可以中途退出的人，也可以卡掉常数不是很优的正解，关键是可以卡掉边界处理不好的人。

但我把它特判了。

@偶耶XJX ！快更新《出题人心理学》！有新点子！

50 pts 代码（可以拍拍后缀数组+rmq）：

#include<set>
#include<map>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define DB double
#define LL long long
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
    while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
    return f * x;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
int f[MAXN];
char ss[MAXN],s1[MAXN],s2[MAXN<<1];
int sa[MAXN<<1],rk[MAXN<<1],ht[MAXN<<1],h[MAXN<<1];
int nx[MAXN<<1],hd[MAXN<<1],tl[MAXN<<1],pr[MAXN<<2];
int ins(int i,int x) {return hd[i]==0 ? (hd[i]=x):(nx[tl[i]]=x);}
void INIT_SA(char *s,int *sa,int *rk,int n) {
    for(int i=1;i<=n;i++)sa[i]=rk[i]=nx[i]=hd[i]=tl[i]=pr[i+n]=0;
    for(int i = 1;i <= n;i ++) {
        nx[tl[(int)s[i]] = ins((int)s[i],i)] = 0;
    }
    int cn = 0,nm = 0;
    for(int i = 0;i <= 256;i ++) {
        int p = hd[i];
        if(p) nm ++;
        while(p) {
            sa[++ cn] = p;
            rk[p] = nm;
            if(p == tl[i]) break;
            p = nx[p];
        } hd[i] = tl[i] = 0;
    }
    for(int ii = 1;ii < n;ii <<= 1) {
        for(int i = 1;i <= n;i ++) pr[i] = rk[i],rk[i]=0;
        for(int i = n-ii+1;i <= n;i ++) {
            nx[tl[pr[i]] = ins(pr[i],i)] = 0;
        }
        for(int i = 1;i <= n;i ++) {
            if(sa[i] <= ii) continue;
            nx[tl[pr[sa[i]-ii]] = ins(pr[sa[i]-ii],sa[i]-ii)] = 0;
        }
        int cn = 0,nm = 0;
        for(int i = 1;i <= n;i ++) {
            int p = hd[i],pp = 0;
            while(p) {
                sa[++ cn] = p;
                rk[p] = (!pp || pr[p+ii] != pr[pp+ii] ? (++nm):nm);
                if(p == tl[i]) break;
                pp = p; p = nx[p];
            } hd[i] = tl[i] = 0;
        }
    }return ;
}
void INIT_HEIGHT(char *s,int *sa,int *rk,int *hi,int n) {
    hi[0] = 0; sa[0] = 0;
    for(int i = 1;i <= n;i ++) {
        int k = sa[rk[i]-1];if(!k) {hi[i]=0;continue;}
        hi[i] = max(0,hi[i-1]-1);
        while(s[i+hi[i]] == s[k+hi[i]]) hi[i] ++;
    }return ;
}
int dp[MAXN<<1][20]; // 18
int hb[MAXN<<1];
int lcp(int l,int r) {
    if(l > r) swap(l,r);
    if(l == r) return n+m;
    int le = hb[r-l];
    return min(dp[l+1][le],dp[r-(1<<le)+1][le]);
}
int main() {
    freopen("mata.in","r",stdin);
    freopen("mata.out","w",stdout);
    n = read(); m = read(); k = read();
    scanf("%s",ss + 1);
    scanf("%s",s1 + 1);
    LL sm = 0;
    for(int i = 1;i <= m;i ++) f[i] = read(),sm += f[i];
    bool flag1 = 1;
    for(int i = 1;i <= n;i ++) if(ss[i] != '1') flag1 = 0;
    for(int i = 1;i <= m;i ++) if(s1[i] != '1') flag1 = 0;
    if(n <= 1000 && m <= 1000) {
        for(int i = 1;i <= n;i ++) {
            int kk = k,pos = i;
            for(int j = 1;j <= m && pos <= n;j ++) {
                if(ss[pos] != s1[j]) kk -= f[j];
                if(kk < 0) break;
                pos ++;
            }
            printf("%d ",pos);
        }ENDL;
        return 0;
    }
    if(flag1 || k >= sm) {
        for(int i = 1;i <= n;i ++) {
            printf("%d ",min(n+1,i+m));
        }ENDL;
        return 0;
    }
    if(k <= 100) {
        for(int i = 1;i <= n;i ++) s2[i] = ss[i];
        for(int i = 1;i <= m;i ++) s2[n+i+1] = s1[i];
        s2[n+1] = '2'; s2[n+m+2] = '3';
        int nle = n+m+1; hb[1] = 0;
        for(int i = 2;i <= nle;i ++) hb[i] = hb[i>>1]+1;
        INIT_SA(s2,sa,rk,nle);
        INIT_HEIGHT(s2,sa,rk,ht,nle);
        for(int i = 1;i <= nle;i ++) dp[i][0] = h[i] = ht[sa[i]];
        for(int i = nle;i > 0;i --) {
            for(int j = 1;j <= 18 && i+(1<<j)-1<=nle;j ++) {
                dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
            }
        }
        for(int i = 1;i <= n;i ++) {
            int ad = i-1,le = 0,la = 0;
            int st = 0,kk = k;
            while(la <= m && i-1+la <= n && kk >= 0) {
                le = lcp(rk[ad+1],rk[n+st+2]);
                ad += le+1; la += le+1;
                st += le+1; kk -= f[la];
            }
            printf("%d ",i+la-1);
        }ENDL;
        return 0;
    }
    return 0;
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

JZM 的印象笔记 （卷积，分块）

题面