https://www.luogu.com.cn/problem/CF1140E

\(DP\)

没有长度为奇数的回文串，必定满足没有长度为\(3\)的回文串

我们要避免\(x,y,x\)的情况

即\(a[i]≠a[i+2]\)

根据这一规律，我们把序列拆成下标分别为奇数和偶数的两个序列分别处理

可以发现，一段\(-1\)的区间的可能性只与其两端的数是否相等有关，故可以预处理出\(dp\)数组。

\(dp[i][0]\)表示长度为\(i\)的-1数列，其两边数相等时的方案数

例：\(x,-1,……,-1(i\)个\(-1),x\)

公式：\(dp[i][0]=dp[i-1][1]*(k-1)\)

\(dp[i][1]\)表示长度为\(i\)的-1数列，其两边数相等时的方案数

例：\(x,-1,……,-1(i\)个\(-1),y\)

公式：\(dp[i][1]=dp[i-1][0]+dp[i-1][1]*(k-2)\)

以上公式可以模拟一下进行推导

然后，把两个串中的\(-1\)区间的贡献相乘即可

注意边界条件的判断(首尾的\(-1\)序列为特殊情况)

经验：

\(1.\)要善于简化题目的条件，将相同的情况合并

\(2.\)注意取摸的题目，运算过程中不要爆\(long\) \(long\)（调了老半天）

\(Code:\)

#include<bits/stdc++.h>
#define mod 998244353
#define N 400005
using namespace std;
long long k,res,dp[N][2],Z[N];
int a[N],c1[N],c2[N];
int F1,F2,last,cnt1=0,cnt2=0,n;
int main() 
{
    scanf("%d%lld",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    dp[0][0]=0;
    dp[0][1]=1;
    for (int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][1]*(k-1)%mod;
        dp[i][1]=(dp[i-1][0]+dp[i-1][1]*(k-2)%mod)%mod;
    }
    Z[0]=1;
    for (int i=1;i<=n;i++)
        Z[i]=Z[i-1]*(k-1)%mod;
    for (int i=1;i<=n;i++)
        if (i&1)
        {
            ++cnt1;
            c1[cnt1]=a[i]; 
            F1+=(a[i]==(-1));
            if (cnt1!=1&&a[i]!=-1&&c1[cnt1-1]==c1[cnt1])
            {
                printf("0\n");
                return 0;
            }
        } else
        {
            ++cnt2;
            c2[cnt2]=a[i];
            F2+=(a[i]==(-1));
            if (cnt2!=1&&a[i]!=-1&&c2[cnt2-1]==c2[cnt2])
            {
                printf("0\n");
                return 0;
            }
        }
    res=1;
    if (F1==cnt1)
        res=res*k%mod*Z[cnt1-1]%mod; else
        {
            last=-1;
            for (int i=1;i<=cnt1;i++)
                if (c1[i]!=-1)
                {
                    if (c1[i-1]==-1)
                    {
                        if (last==1)
                            res=res*((dp[i-2][0]+dp[i-2][1]*(k-1)%mod)%mod)%mod; else
                            res=res*dp[i-last][c1[i]!=c1[last-1]]%mod;
                    }
                    last=-1;
                } else
                {
                    if (last==-1)
                        last=i;
                }
            if (c1[cnt1]==-1)
                res=res*((dp[cnt1-last][0]+dp[cnt1-last][1]*(k-1)%mod)%mod)%mod;
        }
    if (!cnt2)
    {
        printf("%lld\n",res);
        return 0;
    }
    if (F2==cnt2)
        res=res*k%mod*Z[cnt2-1]%mod; else
        {
            last=-1;
            for (int i=1;i<=cnt2;i++)
                if (c2[i]!=-1)
                {
                    if (c2[i-1]==-1)
                    {
                        if (last==1)
                            res=res*((dp[i-2][0]+dp[i-2][1]*(k-1)%mod)%mod)%mod; else
                            res=res*dp[i-last][c2[i]!=c2[last-1]]%mod;
                    }
                    last=-1;
                } else
                {
                    if (last==-1)
                        last=i;
                }
            if (c2[cnt2]==-1)
                res=res*((dp[cnt2-last][0]+dp[cnt2-last][1]*(k-1)%mod)%mod)%mod;
        }
    res=(res%mod+mod)%mod;
    printf("%lld\n",res);
    return 0;
}