欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【递推】codeforces1140E Palindrome-less Arrays

程序员文章站 2022-07-05 14:50:42
...

1140E Palindrome-less Arrays

Let’s denote that some array b is bad if it contains a subarray bl,bl+1,…,br of odd length more than 1 (l<r and r−l+1 is odd) such that ∀i∈{0,1,…,r−l} bl+i=br−i.

If an array is not bad, it is good.

Now you are given an array a1,a2,…,an. Some elements are replaced by −1. Calculate the number of good arrays you can obtain by replacing each −1 with some integer from 1 to k.

Since the answer can be large, print it modulo 998244353.

Input
The first line contains two integers n and k (2≤n,k≤2⋅105) — the length of array a and the size of “alphabet”, i. e., the upper bound on the numbers you may use to replace −1.

The second line contains n integers a1,a2,…,an (ai=−1 or 1≤ai≤k) — the array a.

Output
Print one integer — the number of good arrays you can get, modulo 998244353.


 有一个重要的事实——这个数列没有奇数项的回文串,等价于它没有三项的回文串,也就是说a[i1]̸=a[i+1],(1&lt;i&lt;n)a[i-1] \not = a[i+1],(1&lt;i&lt;n)。为了更方便地化解问题,我们把题目给出的a数列按奇数项和偶数项分成两个数列b与c,则在替换-1之后,b和c中不应该出现相邻相同项。只要把满足条件的b和c的种数相乘,就是所需答案。
 问题变成了怎么求相邻互异的数列总数。先考虑一个子问题,首项已经固定,剩余项总长度为m,取值为1到k的,相邻互异的,而且首尾相同的数列有多少种?假设答案为q[m]q[m],而首尾互异的那些数列总数为p[m]p[m],很容易推导出有,p[i]=(k1)q[i1]+(k2)p[i1],q[i]=p[i1]p[i]=(k-1)*q[i-1]+(k-2)*p[i-1],q[i]=p[i-1],而且p[0]=0,q[0]=1p[0]=0,q[0]=1,递推即可。
 了解这个子问题后,考虑数列中一段连续的-1,倘若后一项和前一项相同,说明最后一个-1与首项不同,答案乘上p[len]p[len],否则如果不同,答案应该乘上q[len]+p[len](k2)/(k1)q[len]+p[len]*(k-2)/(k-1)
 到此为止问题基本解决。另外,注意一下首尾有-1,以及全部为-1的等等特殊情况。

#include<cstdio>
#include<algorithm>
#define mo 998244353
using namespace std;
using LL=long long;

int n,k,ans=1,a[200005],b[100005],c[100005],p[100005],q[100005],inv;

int quick_power(int a, int b)
{
	int res=1,base=a;
	while(b)
	{
		if(b&1)
			res=(LL)res*base%mo;
		base=(LL)base*base%mo;
		b>>=1;
	}
	return res;
}

int main()
{
	scanf("%d%d",&n,&k);
	inv=quick_power(k-1,mo-2);
	p[0]=0,q[0]=1;
	for(int i=1;i<=n+1>>1;i++)
	{
		p[i]=((LL)(k-1)*q[i-1]+(LL)(k-2)*p[i-1])%mo;
		q[i]=p[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(i&1)
			b[i+1>>1]=a[i];
		else
			c[i+1>>1]=a[i];
	}
	int i=1;
	while((i<=n+1>>1)&&b[i]==-1)
		i++;
	for(int j=1;j<i;j++)
		ans=(LL)ans*(k-1)%mo;
	if(i>n+1>>1)
		ans=(LL)ans*k%mo*inv%mo;
	for(int j;i<=n+1>>1;i=j)
	{
		j=i+1;
		while((j<=n+1>>1)&&b[j]==-1)
			j++;
		if(j>n+1>>1)
			for(int g=i+1;g<j;g++)
				ans=(LL)ans*(k-1)%mo;
		else if(b[i]==b[j])
			ans=(LL)ans*p[j-i-1]%mo;
		else
			ans=(LL)ans*(q[j-i-1]+(LL)p[j-i-1]*(k-2)%mo*inv%mo)%mo;
		j-i;
	}
	i=1;
	while((i<=n>>1)&&c[i]==-1)
		i++;
	for(int j=1;j<i;j++)
		ans=(LL)ans*(k-1)%mo;
	if(i>n>>1)
		ans=(LL)ans*k%mo*inv%mo;
	for(int j;i<=n>>1;i=j)
	{
		j=i+1;
		while((j<=n>>1)&&c[j]==-1)
			j++;
		if(j>n>>1)
			for(int g=i+1;g<j;g++)
				ans=(LL)ans*(k-1)%mo;
		else if(c[i]==c[j])
			ans=(LL)ans*p[j-i-1]%mo;
		else
			ans=(LL)ans*(q[j-i-1]+(LL)p[j-i-1]*(k-2)%mo*inv%mo)%mo;
		j-i;
	}	
	printf("%d",ans);
	return 0;
}
相关标签: 递推