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