题解：P11959 「ZHQOI R1」诗歌

yingkeqian9217 · 2025-03-22 20:56:25 · 题解

赛时做法，不知道官方题解为什么这么复杂，赶紧来发个题解。

显然一个串是动听的充要条件是任意两个相同字符坐标差超过 m+2，即任意连续 m+3 个字符两两不同。

注意到开头已经给了 m+2 个字符，这启示我们直接往后填，不考虑末位字符的限制，每次要求与前面 m+2 个字符均不同，有 (k-(m+2))^{n-(m+2)} 种方案。

对每种字符进行考虑，如果这个字符在开头 i 处出现过，则只会在 i+m+3\sim n 这一段再次出现，将 m+3\sim i+m+2 任意填上后，转化为一个只与余下长度有关而与当前字符无关的问题。

显然可以不考虑已确定的末位字符 x，然后考虑指定一些位置放 x，显然相邻位置差以及与末位的差都至少为 m+2，进一步地，如果一个位置之前 m+2 位有 x，直接 k-(m+2) 任意填，否则额外要求与 x 不同，k-(m+2)-1 种方案。

可以直接 dp，f_i 表示前 i 位的答案，有转移 f_i=(k-(m+2)-1)f_{i-1}+(k-(m+2))^{m+2}f_{i-m-1}。

时间复杂度 O(n+qm)，跑挺快的。

#include<bits/stdc++.h>
#define maxn 2010
#define int long long
using namespace std;
const int Mod=998244353,N=1e7;
inline int reduce(int x){if(x>=Mod) return x-=Mod;return x;}

int q,k,m,f[N+100],bas[maxn];
inline int query(int x){
    if(x<0) return 0;
    return f[x];
}
inline void solve(){
    int res=1;
    scanf("%lld%lld%lld",&q,&k,&m);
    m+=2;
    bas[0]=1;
    for(int i=1;i<=m;i++) bas[i]=bas[i-1]*(k-m)%Mod;
    f[0]=1;
    for(int i=1;i<=N;i++){
        if(i>m) f[i]=(f[i-1]*(k-m-1)+f[i-m-1]*bas[m])%Mod;
        else f[i]=f[i-1]*(k-m-1)%Mod;
    }
    while(q--){
        int n;
        scanf("%lld",&n);
        unordered_map<int,int>mp;
        for(int i=1,x;i<=m;i++) scanf("%lld",&x),mp[x]=i;
        int len,ans=0;
        scanf("%lld",&len);
        while(len--){
            int x;
            scanf("%lld",&x);
            if(!mp.count(x)) ans=reduce(ans+query(n-m-1));
            else ans=(ans+query(n-mp[x]-m-1)*bas[mp[x]])%Mod;
        }
        printf("%lld\n",ans);
    }
}
signed main(){
    signed C,T=1;
    scanf("%d",&C);
    while(T--) solve();
    return 0;
}