【递推】codeforces1140E Palindrome-less Arrays
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数列按奇数项和偶数项分成两个数列b与c,则在替换-1之后,b和c中不应该出现相邻相同项。只要把满足条件的b和c的种数相乘,就是所需答案。
问题变成了怎么求相邻互异的数列总数。先考虑一个子问题,首项已经固定,剩余项总长度为m,取值为1到k的,相邻互异的,而且首尾相同的数列有多少种?假设答案为,而首尾互异的那些数列总数为,很容易推导出有,,而且,递推即可。
了解这个子问题后,考虑数列中一段连续的-1,倘若后一项和前一项相同,说明最后一个-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;
}
上一篇: 91. 解码方法