Educational Codeforces Round 62 (Rated for Div. 2) - E.Palindrome-less Arrays（dp）
题目大意：给你一个串，这个串有-1或1~k中的数组成，-1位置的数未确定，你可以将1~k中的数填入其中。问有多少种填的方案使得这个串中不包含回文串
思路：这道题看的时候就感觉是dp，不过搞了很长时间没搞出来（菜哭）。看了cf官方的题解后恍然大悟。
首先需要知道只要长度为3的串不是回文串，那么包含这个长度为3的串的较长的串一定不是回文串（这个很好理解）
所以我们只需消灭长度为3的回文串。通过观察易得下标为奇数的数字和下标为偶数的数字是互不影响的，所以可以将这个数列分成奇数列和偶数列，最后答案就是两个答案的乘积
我们需要找出每个字符(i处)之后的第一个不是-1的数，记做Nx[i],如果后面全是-1,那么Nx[i]=n(n是数列长度,这里假定下标从1开始，我的代码里是从零开始的)
设dp[i][0/1]为对于有连续的i个-1的两边的数不是-1的串，两边的数相等（1）或不相等（0）构成的方案数
如 3 -1 -1 -1 2即为dp[3][0], 4 -1 -1 4为dp[2][1]
这道题主要分以下几种情况(下面的x代表-1)
1.xxxxxxxx（共有i个-1）
一个子串全由-1组成，那么有
方案数=k*dp[i-2][1]+k*k-1*dp[i-2][0]
或者为k*pow(k-1,i-1)
2.axxxxxxx (共有i个-1)
也就是这个串一端是-1，另一端不是-1
方案数=dp[i-1][1]+k-1*dp[i-1][0]
或者为pow(k-1,i)
3.xxxxxxxxa(共有i个-1)
同上
4.axxxxxxxxxb(共有i个-1)
这里要分i是奇数还是偶数
i为奇数：
dp[i][1]=dp[i/2][1]*dp[i/2][1])+k-1*dp[i/2][0]*dp[i/2][0]
dp[i][0]=2*dp[i/2][1]*dp[i/2][0]+(k-2)*dp[i/2][0]*dp[i/2][0]
i为偶数：
dp[i][1]=(k-1)*dp[i-1][0]
dp[i][0]=dp[i-1][1]+(k-2)*dp[i-1][0]
这道题到这里就基本完成了，接下来就是把每一段的结果都用上面的这些公式求出来，把他们乘起来就可以了，别忘了每一步运算都需要取模
题目大意：给你一个串，这个串有-1或1~k中的数组成，-1位置的数未确定，你可以将1~k中的数填入其中。问有多少种填的方案使得这个串中不包含回文串
思路：这道题看的时候就感觉是dp，不过搞了很长时间没搞出来（菜哭）。看了cf官方的题解后恍然大悟。
首先需要知道只要长度为3的串不是回文串，那么包含这个长度为3的串的较长的串一定不是回文串（这个很好理解）
所以我们只需消灭长度为3的回文串。通过观察易得下标为奇数的数字和下标为偶数的数字是互不影响的，所以可以将这个数列分成奇数列和偶数列，最后答案就是两个答案的乘积
我们需要找出每个字符(i处)之后的第一个不是-1的数，记做Nx[i],如果后面全是-1,那么Nx[i]=n(n是数列长度,这里假定下标从1开始，我的代码里是从零开始的)
设dp[i][0/1]为对于有连续的i个-1的两边的数不是-1的串，两边的数相等（1）或不相等（0）构成的方案数
如 3 -1 -1 -1 2即为dp[3][0], 4 -1 -1 4为dp[2][1]
这道题主要分以下几种情况(下面的x代表-1)
1.xxxxxxxx（共有i个-1）
一个子串全由-1组成，那么有
方案数=k*dp[i-2][1]+k*k-1*dp[i-2][0]
或者为k*pow(k-1,i-1)
2.axxxxxxx (共有i个-1)
也就是这个串一端是-1，另一端不是-1
方案数=dp[i-1][1]+k-1*dp[i-1][0]
或者为pow(k-1,i)
3.xxxxxxxxa(共有i个-1)
同上
4.axxxxxxxxxb(共有i个-1)
这里要分i是奇数还是偶数
i为奇数：
dp[i][1]=dp[i/2][1]*dp[i/2][1])+k-1*dp[i/2][0]*dp[i/2][0]
dp[i][0]=2*dp[i/2][1]*dp[i/2][0]+(k-2)*dp[i/2][0]*dp[i/2][0]
i为偶数：
dp[i][1]=(k-1)*dp[i-1][0]
dp[i][0]=dp[i-1][1]+(k-2)*dp[i-1][0]
这道题到这里就基本完成了，接下来就是把每一段的结果都用上面的这些公式求出来，把他们乘起来就可以了，别忘了每一步运算都需要取模
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
ll n,k;
ll a[200010];
ll Nxb[200010];
ll Nxc[200010];
ll dp[200010][2];
vector<ll> b;
vector<ll> c;
int lenb,lenc;
ll ansb,ansc;
ll Mul(ll a,ll b)
{return (a*b)%MOD;
}
ll powermod(ll x,ll n)
{ll res=1;while(n>0){if(n&1){res=(res*x)%MOD;}x=(x*x)%MOD;n>>=1;}return res;
}
void init()
{dp[0][1]=0;dp[0][0]=1;for(int i=1;i<200010;i++){if(i%2==1){dp[i][1]=(Mul(dp[i/2][1],dp[i/2][1])+Mul(k-1,Mul(dp[i/2][0],dp[i/2][0])))%MOD;dp[i][0]=(Mul(Mul(2,dp[i/2][1]),dp[i/2][0])+Mul(k-2,Mul(dp[i/2][0],dp[i/2][0])))%MOD;}else{dp[i][1]=Mul(k-1,dp[i-1][0]);dp[i][0]=(dp[i-1][1]+Mul(k-2,dp[i-1][0]))%MOD;}}
}
ll cal(int s,int e,vector<ll> &v)
{int len;if(s==e){if(v[s]==-1)return k;elsereturn 1; }if(v[s]==-1&&v[e]==-1){ len=e-s+1;return (Mul(k,dp[len-2][1])+Mul(Mul(k,k-1),dp[len-2][0]))%MOD;
// return Mul(k,powermod(k-1,len-1));}if(v[s]==-1&&v[e]!=-1){len=e-s;return (dp[len-1][1]+Mul(k-1,dp[len-1][0]))%MOD;
// return powermod(k-1,len);}if(v[s]!=-1&&v[e]==-1){len=e-s;return (dp[len-1][1]+Mul(k-1,dp[len-1][0]))%MOD;
// return powermod(k-1,len);}if(v[s]!=-1&&v[e]!=-1){len=e-s-1;if(v[s]==v[e])return dp[len][1];elsereturn dp[len][0];}
}
void solveb()
{int u=0;int ls=0;ansb=1;if(b.size()==1){if(b[0]==-1)ansb=k;elseansb=1;}while(u<=lenb-1){if(u==lenb-1&&u==Nxb[u])break;ls=Nxb[u];ansb=Mul(ansb,cal(u,ls,b));u=ls;}
}
void solvec()
{int u=0;int ls=0;ansc=1;if(c.size()==1){if(c[0]==-1)ansc=k;elseansc=1;}while(u<=lenc-1){if(u==lenc-1&&u==Nxc[u])break;ls=Nxc[u];ansc=Mul(ansc,cal(u,ls,c));u=ls;}
}
int main()
{cin >> n >> k;init();for(int i=1;i<=n;i++)cin >> a[i];for(int i=1;i<=n;i+=2)b.push_back(a[i]);for(int i=2;i<=n;i+=2)c.push_back(a[i]);lenb=b.size();lenc=c.size();for(int i=lenb-1;i>=0;i--){if(i+1>lenb-1)Nxb[i]=lenb-1;else{if(b[i+1]==-1){Nxb[i]=Nxb[i+1];}else{Nxb[i]=i+1;}}}for(int i=lenc-1;i>=0;i--){if(i+1>lenc-1)Nxc[i]=lenc-1;else{if(c[i+1]==-1){Nxc[i]=Nxc[i+1];}else{Nxc[i]=i+1;}}}solveb();solvec();
// cout << ansb << " "<<ansc << endl;cout << Mul(ansb,ansc) << endl;return 0;
}