[数据结构与算法]E. Palindrome-less Arrays（思维dp、拆分序列、回文）

传送门

题解

分析：
给出一个长度为n的数组，其中有若干个-1，需要用1~k中的数去替换所有的-1，使得数组序列中不存在长度为奇数(>3)的回文序列
2 3 2, 2 2 2,…1 2 3 2 1…,观察可发现,不存在长度为奇数的回文序列等价于$a[i]!=a[i+2]，a[i]与a[i+1]$没有限制关系，这样一来可以把序列拆成奇数下标和偶数下标对应元素分别组成的两个子序列
$最后的方案数=奇序列填补方式?奇序列填补方式$
那么对于子序列，该满足的条件就是 相邻元素不相等
如何选取1~k中的数去替换序列中所有的-1,以达到上述要求呢
2 -1 3 -1 -1 3 -1 -1 4
第1个-1选法k-2, (根据这个-1两段的数字,不能选2、3),第2个-1,乍一看不能确定,因为后面连着-1，那如果多个-1连成一块
又该如何确定方案数呢？ 我们把连续的-1当成一块，因为这块-1的位置 会相互影响
$先看一块中有2个负1,第1个负1有k?1种，第2个负1有k?2种$
而3 -1 -1 4 这块负1中,第1个负1有k-1种，第2个负1的种数就要分类讨论了
$若第1个负1填4,第2个负1有k?1种;若第1个?1负1不填4,第2个负1有k?2种$
需要分类讨论，-1块的规模一大就需要多重的分类讨论，于是想到dp递推
方案数取决于-1块两端的两个数是否相等

• 如果相等，$dp[i][1]=dp[i?1][0]?(k?1)$
  因为 3 -1 -1……-1 -1 3,最后一个-1有k-1种方案,剩余的连续的i-1个-1
  也就是一个长度为i-1的f-1块，首尾两段只能不相等，
  因为最后一个-1不可能取3
• 如果不相等，$dp[i][0]=dp[i?1][0]?(k?2)+dp[i?1][1]?1$
  因为3 -1 -1……-1 -1 4首尾不相等，前面长度为i-1的-1块首尾两段
  既可能相等也可能不相等，相等时，最后一个-1必然取3
  不相等,最后一个-1有k-2种取法

(在状态表示中除了-1块的长度，多加一层表示两段是否相等)
完成该子序列的方式自然就是各块-1

//#include <bits/stdc++.h>
#include <iostream> 
using namespace std;
#define int long long
const int N=3e5+5;
const int mod=998244353; 
int n,k;
int w[N];
int a[N];//奇数下标对应的序列 
int b[N];//偶数下标 
int f[N][2];//长度为i的-1块 
int quickpow(int b,int e){
	b%=mod;
	e%=mod;
	int res=1;
	while(e){
		if(e&1)res=res*b%mod;
		b=b*b%mod;
		e>>=1;
	}
	return res;
}

int solve(int v[],int n){//n优先取的是形参而不是全局变量 
	if(!n)return 1;
	if(n==1){
		if(v[n]!=-1)return 1;
		else return k;
	}
	int res=0; 
//	int pre=0;//上一个非-1的数
//	v[0]=3e5;//一个不存在的数 ,不行，要特殊处理两端存在的-1
	int l=1,r=n;
	while(l<=n&&v[l]==-1){
		l++;//l最终指向第一个 不是-1的数 
	} 
	while(r>=1&&v[r]==-1){
		r--;//r最终指向最后一个 不是-1的数 
	} 
	if(l>n)return quickpow(k-1,n-1)*k%mod;//n个-1
//	l-1个-1，n-r个-1
	res=quickpow(k-1,l-1)*quickpow(k-1,n-r)%mod;//都受到一端的限制
	
	int pre=l; 
	for(int i=l+1;i<=r;i++){
		if(v[i]==-1)continue;
		else{//1 -1 -1 4
			int m=i-pre-1;//-1块的长度 
			res=res*f[i-pre-1][(v[pre]==v[i])]%mod;
			pre=i; 
		}
	}
	
	return res; 
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>w[i];
//	初始化-1块对应的方案数,-1块的长度至少为1 
	f[0][0]=1;//因为f[1][1]一定为k-1且f[1][1]要由f[0][0]推来 
	f[0][1]=0;//因为f[1][0]定为k-2且f[1][0]要由f[0][0]=1和f[0][0]推来 
	for(int i=1;i<=n;i++){
		f[i][1]=f[i-1][0]*(k-1)%mod;
		f[i][0]=(f[i-1][0]*(k-2)+f[i-1][1]*1)%mod; 
	}
	for(int i=1;i<=n;i++){
		if(i&1)a[++a[0]]=w[i];//a[0]做哨兵，最后存储的就是a数组长度
		else b[++b[0]]=w[i]; 
	} 
	cout<<solve(a,a[0])*solve(b,b[0])%mod;

	return 0;
}

另一种递推方式

算是另一种递推啦
待看做法

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖