E. Palindrome-less Arrays
E. Palindrome-less Arrays
题意：给定一串数字 不确定的地方用-1 表示 确定的就有确切的数字 不能有大于1的奇回文串 问在-1的地方填数字 可以填1---k 有多少种填法
思路 ：由不能有大于1的奇回文串 等价于 奇数序号的数字相邻不能相等 偶数序号的数字相邻不能相等 分解出来即可、
然后进行状态定义 dp[i][0/1] 表示i位置和下一个确定数字的数字相同的填法（第二维是1） 和不同的填法（第二维是0）
需要特殊处理开始和结尾 即 ：- 1 -1 -1 -1 A A表示已经确定的数字 开头的可能性为pow(k-1,有多少个1) 结尾类似
其余的确定数字之前的段可以提取出来分段dp 乘法原理乘起来即可
中间转移为 dp[i][1]=dp[i-1][0]
dp[i][0]=dp[i-1][0]*(k-2)+dp[i-1][1]*(k-1)
这里其实就是分类讨论的思想 如果dp只有一维的话那么后面的数字就会影响前面 产生后效性
那么怎么取消这种后效性呢？那就是对后面的数字进行分类讨论 相当于已经确定了后面的数字
所以前面填数字的时候就可以根据分类讨论的类别来进行转移 就可以取消后效性了
#include<bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))
#define F first
#define S second
#define pii pair<long long ,long long >
#define mkp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const ll mod=998244353;
long long a[maxn];
long long dp[maxn][2];
ll n,k;
vector<ll>even,odd;
vector<ll>even_div,odd_div;
long long solve(const vector<ll>&a,const vector<ll>&div,int flag){
long long ans=1;
if(div.size()==0){
ans=k;
ans%=mod;
for(int i=1;i<a.size();i++){
ans*=(k-1);
ans%=mod;
}
return ans;
}
if(div[0]!=0){
for(int i=0;i<div[0];i++){
ans*=(k-1);
ans%=mod;
}
}
MS(dp,0);
for(int z=0;z<div.size()-1;z++){
//cout<<a[div[z]]<<" what ? "<<a[div[z+1]]<<endl;
if(a[div[z]]!=a[div[z+1]]){
dp[div[z]][1]=0;
dp[div[z]][0]=1;
}
else dp[div[z]][1]=1,dp[div[z]][0]=0;
}
for(int z=1;z<div.size();z++){
//int zz=0;
if(a[div[z-1]]!=a[div[z]])dp[div[z-1]][0]=1;
for(int i=div[z-1]+1;i<div[z];i++){
// zz=1;
//if(i!=div[z]-1)dp[i][0]=(((dp[i-1][1]+dp[i-1][0])%mod)*(k-1)%mod);
dp[i][0]=(((dp[i-1][0]*(k-2)%mod)+(dp[i-1][1]*(k-1)%mod))%mod);
// cout<<i<<" ?? "<<dp[i-1][0]<<" *** "<<dp[i-1][1]<<endl;
dp[i][1]=dp[i-1][0]%mod;
}
ans=((ans*dp[div[z]-1][0])%mod);
}
for(int i=div[div.size()-1]+1;i<a.size();i++){
ans*=(k-1);
ans%=mod;
}
//cout<<ans<<endl;
return ans;
}
int main(){
scanf("%lld%lld",&n,&k);
FOR(i,1,n)scanf("%lld",&a[i]);
for(int i=1;i<=n;i+=2){
odd.push_back(a[i]);
}
for(int i=2;i<=n;i+=2){
even.push_back(a[i]);
}
for(int i=0;i<odd.size();i++){
if(odd[i]!=-1)odd_div.push_back(i);
if(i!=0&&odd[i]==odd[i-1]&&odd[i]!=-1){
cout<<0<<endl;
return 0;
}
}
for(int i=0;i<even.size();i++){
if(i!=0&&even[i]==even[i-1]&&even[i]!=-1){
cout<<0<<endl;
return 0;
}
if(even[i]!=-1)even_div.push_back(i);
}
long long temp1,temp2;
temp1=solve(odd,odd_div,1);
temp2=solve(even,even_div,0);
cout<<((temp1%mod)*(temp2%mod))%mod<<endl;
return 0;
} 
投递欣旺达等公司6个岗位 >
