题目链接:http://codeforces.com/contest/1140/problem/E
题目大意
给定一个序列其中有若干个-1值，-1值可填的数是1到k，
然后定义一个奇回文，长度不为1且是奇数的回文串，
问原序列中不含奇回文的子串的组合数是多少。
题目分析
这道题我看题解的初步提示才反应过来。。。
还是蛮思维的，由于是奇数回文，刚开始想情况比较多比较复杂，
但是可以发现等价条件其实就是看相隔一位的两个数是否能相等，
那么我们把原串按奇偶位置划分，对每个新子串，进行DP计数。
计数的思想也很巧妙，一维DP状态是表示不了全部情况的，
但是二维空间大小又是限制，所以把第二维限制在两端的状态，
对于一个-1连续串，其两端如果字母都存在，那么分类，
如果字母相等: dp[i][0]=(k-1)*dp[i-1][1];
如果不等: dp[i][1]=dp[i-1][0]+(k-1)*dp[i-1][1];
至于只有一端有数字的情况，可以类似讨论，不难得出式子，两端都无字母的话
计数直接是有规律的，详见代码。
时间复杂度：O(n);
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll __int64#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=998244353;
const int maxn=2e5+100;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
给定一个序列其中有若干个-1值，-1值可填的数是1到k，
然后定义一个奇回文，长度不为1且是奇数的回文串，
问原序列中不含奇回文的子串的组合数是多少。题目分析：
这道题我看题解的初步提示才反应过来。。。
还是蛮思维的，由于是奇数回文，刚开始想情况比较多比较复杂，
但是可以发现等价条件其实就是看相隔一位的两个数是否能相等，
那么我们把原串按奇偶位置划分，对每个新子串，进行DP计数。
计数的思想也很巧妙，一维DP状态是表示不了全部情况的，
但是二维空间大小又是限制，所以把第二维限制在两端的状态，
对于一个-1连续串，其两端如果字母都存在，那么分类，
如果字母相等: dp[i][0]=(k-1)*dp[i-1][1];
如果不等: dp[i][1]=dp[i-1][0]+(k-1)*dp[i-1][1];
至于只有一端有数字的情况，可以类似讨论，不难得出式子，两端都无字母的话
计数直接是有规律的，详见代码。
时间复杂度：O(n);
*/
int n,k,a[maxn];
int idx[2],tmp[2][maxn];
ll dp[maxn][4];
ll solve(int x){rep(i,0,idx[x]-1) if(tmp[x][i]==tmp[x][i+1]&&tmp[x][i]!=-1) return 0;ll ret=1;int i=0;for(i=0;i<idx[x];i++){if(tmp[x][i]==-1){int cnt=0,tp=i;while(i<idx[x]&&tmp[x][i]==-1)i++,cnt++;if(tp==0&&i==idx[x]) ret=ret*dp[cnt][3]%mod;else if(tp==0||i==idx[x]) ret=ret*dp[cnt][2]%mod;else{if(tmp[x][tp-1]==tmp[x][i]) ret=ret*dp[cnt][0]%mod;else ret=ret*dp[cnt][1]%mod;}}}return ret;
}
int main(){cin>>n>>k;mst(idx,-1);dp[0][0]=0,dp[0][1]=dp[0][2]=dp[0][3]=1;rep(i,1,maxn){dp[i][0]=1LL*(k-1)*dp[i-1][1]%mod;dp[i][1]=(dp[i-1][0]+1LL*(k-2)*dp[i-1][1]%mod)%mod;dp[i][2]=(dp[i-1][0]+1LL*(k-1)*dp[i-1][1]%mod)%mod;dp[i][3]=(i==1)?k:1LL*(k-1)*dp[i-1][3]%mod;}rep(i,0,n){cin>>tmp[i&1][i>>1];idx[i&1]=(i>>1)+1;}cout<<solve(0)*solve(1)%mod<<'\n';return 0;
}