题解归档 - cf535D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf535D
• 本地来源：problems/cf535D/idea.md
• 题目链接：https://codeforces.com/contest/535/problem/D
• 原始标题：CF535D — Tavas and Malekas

思路

CF535D — Tavas and Malekas

Catalog 缺口题 · lib_target: 字符串(KMP).cpp

题意

给定 s 长度 n、模式串 p、以及 Malekas 记录的匹配起点子序列 y_1 < … < y_m（y 是 s 中全部 p 出现位置的某个子序列）。求有多少个不同的 s 满足条件，模 10^9+7。

思路

1. 固定字符：若要求 p 在位置 y_i 出现，则 s[y_i … y_i+|p|-1] 被固定为 p。

2. 相邻记录的重叠：对相邻 y_{i-1}, y_i，间距 delta = y_i - y_{i-1}。

   • delta ≥ |p|：两段不重叠，新增 |p| 个固定字符。
   • delta < |p|：两段重叠 |p|-delta 个字符；仅当该重叠等于 p 的某个 border（前缀=后缀）时才合法，否则答案为 0。
3. KMP 前缀函数：沿 border 链构造数组 v：v[k] 表示从链上第 0 层走到第 k 层累计新增的固定字符数；若 delta 不在 v 中则矛盾。
4. 统计：无矛盾时，未固定位置数为 n - cur，答案 26^{n-cur} mod MOD。m=0 时 cur=0。

复杂度

• 时间 O(n + |p|)（KMP 预处理 + 遍历 y）
• 空间 O(|p|)

样例

• n=6, p=ioi, y={1,3}：固定 5 位，余 1 位自由 → 26
• n=5, p=ioi, y={1,2}：delta=1 非合法 border → 0

参考

• CF Round #299 Editorial（536B 同套路，本题编号 535D）

代码

来源：problems/cf535D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 12:00:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1000005,mod=1e9+7;
ll pi[maxn+5],v[maxn+5],y[maxn+5];
string p;
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ans;
}
int main(){
    ll n,m,i,j,k,zc,pd,cur,dq,cnt,ans,lp,vcnt,delta;
    cin>>n>>m>>p;
    lp=p.size();
    for(i=1;i<lp;i++){
        j=pi[i-1];
        while(j>0 and p[j]!=p[i]) j=pi[j-1];
        if(p[j]==p[i]) j++;
        pi[i]=j;
    }
    vcnt=0,v[0]=0,i=lp;
    while(i>=1){
        vcnt++;
        v[vcnt]=v[vcnt-1]+i-pi[i-1];
        i=pi[i-1];
    }
    for(i=1;i<=m;i++) cin>>y[i];
    cur=0;
    for(i=1;i<=m;i++){
        if(i==1) cur+=lp;
        else{
            delta=y[i]-y[i-1];
            if(delta>=lp) cur+=lp;
            else{
                pd=-1;
                for(j=1;j<=vcnt;j++) if(v[j]==delta){pd=j;break;}
                if(pd==-1){
                    cout<<"0\n";
                    return 0;
                }
                cur+=v[pd];
            }
        }
    }
    if(cur>n){
        cout<<"0\n";
        return 0;
    }
    cout<<qpow(26,n-cur)<<"\n";
    return 0;
}