题目大意：给你一个不超过20万的序列，里面每个数都是1到k直接的数，有些是-1，表示这个位置上的数待定。 定义一个序列是“好的”，当这个序列中没有长度为奇数(至少是3)的回文串。问有多少中填法，使得序列是好的。

 

思路；由于是奇数的回文串，所以我们只要考虑是否有长度为3的回文就可以了，那么这个问题就简单了。类似于染色问题，我做了一个dp。

 

 1 #include<bits/stdc++.h>
 2 using namespace std;  
 3 #define rep(i,a,b) for(int i=a;i<=b;i++) 
 4 #define Rep(i,a,b) for(int i=a;i>=b;i--) 
 5 #define ms(i,a)    memset(a,i,sizeof(a))  
 6 #define gc()       getchar() 
 7 #define ll         long long 
 8 template<class T>void read(T &x){
 9     x=0; char c=0; int w=0; 
10     while (!isdigit(c)) w+=c=='-',c=gc();  
11     while (isdigit(c)) x=x*10+(c^48),c=gc(); 
12     if(w) x=-x;  
13 }
14 int const N=200000+3;  
15 int const mod=998244353;  
16 int n,k,a[N],b[N],m;   
17 ll dp[N][2],f[N][3],pw[N];  
18 ll  solve(){
19     int l=-2,r=-2,num=0;
20     ll ret=1;   
21     b[m+1]=-2;  
22     rep(i,1,m-1) if(b[i]>-1 && b[i+1]>-1 && b[i]==b[i+1]) return 0;  
23     rep(i,1,m+1){
24         if (b[i]==-1) num++; 
25         else{
26             r=b[i];  
27             if(num){
28                 if(l<0 && r<0) ret=ret*pw[num-1]% mod *k %mod;   
29                 else if(l>0 && r>0) {
30                     if(l==r) ret=ret*dp[num][1]% mod;  
31                     else ret=ret*(f[num][1]+f[num][0])% mod;  
32                 }else ret=ret*pw[num]% mod;  
33             }
34             l=b[i]; num=0;  
35         } 
36     }
37     return ret;  
38 }  
39 int main(){
40     read(n); read(k); 
41     rep(i,1,n) read(a[i]);  
42     pw[0]=1; rep(i,1,n) pw[i]=pw[i-1]*(k-1)%mod;  
43     dp[1][0]=0; dp[1][1]=k-1;  
44     rep(i,2,n) dp[i][0]=dp[i-1][1],dp[i][1]=(dp[i-1][0]*(k-1)+dp[i-1][1]*(k-2)) % mod;  
45     f[1][0]=k-2;f[1][1]=0; f[1][2]=1;  
46     rep(i,2,n) {
47         f[i][1]=(f[i-1][0]+f[i-1][2])% mod;  
48         f[i][2]=(f[i-1][0]+f[i-1][1])% mod;  
49         f[i][0]=(f[i-1][0]*(k-3)+  f[i-1][1]*(k-2) +f[i-1][2]*(k-2)) % mod;  
50     }
51     rep(i,1,n) if(i&1) b[++m]=a[i];  
52     ll ans=solve();  
53     m=0;  
54     rep(i,1,n) if(i%2==0) b[++m]=a[i];  
55     ans=ans* solve() % mod;  
56     printf("%lld\n",ans); 
57     return 0; 
58 }

View Code