题解：P11959 「ZHQOI R1」诗歌

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

显然一个串是动听的充要条件是任意两个相同字符坐标差超过

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)

，跑挺快的。

CPP

#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;
}

题解：P11959 「ZHQOI R1」诗歌

文章操作

相关推荐

评论

题解：P11959 「ZHQOI R1」诗歌