題意：給定一個(gè)沒有填完的序列，數(shù)值為-1表示你可以用 1~k 中的數(shù)字去覆蓋它，求將該序列填充后，不存在長(zhǎng)度為奇數(shù)的回文串的方案數(shù)

分析：

使之不存在長(zhǎng)度為奇數(shù)的回文串，只需要滿足不存在長(zhǎng)度為3的回文串即可。換句話說：\(a[i] \neq a[i+2]\) 對(duì)所有的 \(i\) 成立。可以發(fā)現(xiàn) i 為奇數(shù)與 i 為偶數(shù)是互不影響的。所以可以把它劃分為兩個(gè)串

一個(gè)串由 $a_1,a_3,a_5, \dots $組成

另一個(gè)串由$ a_2,a_4,a_6,\dots$ 組成

現(xiàn)在問題轉(zhuǎn)化為了：給定一個(gè)序列，將其數(shù)值為-1的位置換為1~k中的數(shù)字，使得序列中兩兩相鄰數(shù)字不同的方案數(shù)。不妨換個(gè)角度想，任何一組連續(xù)的 -1（長(zhǎng)度可以為0或1），兩邊都只有四種情況

兩邊都沒有數(shù)字（即整個(gè)串都是-1）

兩邊中有一邊沒有沒有（只有整個(gè)串的左右兩端有這種情況）

兩邊的數(shù)字相同

兩邊的數(shù)字不同

另外我們可以發(fā)現(xiàn)，前兩種情況可以由后兩種情況推出來，所以只需預(yù)處理把 0~ (n/2)+1長(zhǎng)度的-1串的方案數(shù)都預(yù)處理出來，問題就迎刃而解了。

設(shè)\(d(i,j)\) 表示長(zhǎng)度為 \(i\) 的 -1 串，j 為0 表示兩邊數(shù)字相同，為1表示兩邊數(shù)字不同時(shí)的方案數(shù)，\(d[0][0] = 0, d[0][1] = 1\), 有轉(zhuǎn)移方程：

• \(i\) 為奇數(shù)
  • \(d[i][0] = d[i/2][0]*d[i/2][0] + (k-1)*d[i/2][1]*d[i/2][1]\)
  • \(d[i][1] = d[i/2][0]*d[i/2][1]*2 + (k-2)*d[i/2][1]*d[i/2][1]\)
• \(i\) 為偶數(shù)
  • \(d[i][0] = (k-1)*d[i-1][1]\)
  • \(d[i][1] = d[i-1][0] + (k-2)*d[i-1][1]%mod\)

對(duì)于 i 為奇數(shù)的情況，我們可以取出這個(gè)序列的中間位置 mid，當(dāng) -1 串兩端數(shù)字相同且都等于 x 時(shí)，先假設(shè)mid數(shù)字與x相同，那就轉(zhuǎn)換為了兩個(gè)長(zhǎng)度為 i/2，序列兩端相同 的子問題，然后假設(shè) mid 與 x不同，那么就有(k-1)種方法，可以同樣轉(zhuǎn)換成兩個(gè)長(zhǎng)度為 i/2 ，序列兩端不同的子問題。當(dāng) -1 串兩端數(shù)字不同時(shí)，同理。

預(yù)處理d數(shù)組之后，就可以對(duì)我們之前分好的奇偶串做處理了。思路就是記錄上一個(gè)不為-1的位置。然后最后做一下特判，就可以得到正確答案了。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 998244353; ll d[100010][2]; int a[100010],b[100010]; ll n,k; ll solve(int *a,ll len){ll res = 1;ll last = 0;for(ll i=1;i<=len;i++){if(a[i] == -1)continue;else{if(i == 1){last = i;continue;}if(last == 0){res = res * (d[i-2][0] + (k-1)*d[i-2][1])%mod;}else{if(a[i] == a[last]){res = res * d[i-last-1][0]%mod;}else res = res * d[i-last-1][1]%mod;}last = i;}}if(last==0){res = k;for(int i=2;i<=len;i++)res = (res*(k-1))%mod;}else if(last !=len){res = res * (d[len-last-1][0] + (k-1)*d[len-last-1][1]%mod)%mod;}return res; } int main(){scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++){if(i&1)scanf("%d",&a[(i+1)/2]);else scanf("%d",&b[i/2]);}d[0][0] = 0;d[0][1] = 1;for(int i=1;i<=(n+1)/2;i++){if(i&1){int len = i/2;d[i][0] = (d[len][0] * d[len][0]%mod + (k-1) * d[len][1]%mod * d[len][1]%mod)%mod;d[i][1] = (d[len][0] * d[len][1]%mod * 2%mod + (k-2) * d[len][1]%mod * d[len][1]%mod)%mod;}else{d[i][0] = (d[i-1][1] * (k-1)) % mod;d[i][1] = (d[i-1][0] + (k-2) * d[i-1][1]%mod)%mod;}}printf("%lld\n",(solve(a,(n+1)/2)*solve(b,n-(n+1)/2))%mod);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/1625--H/p/10660923.html

總結(jié)

以上是生活随笔為你收集整理的CF-1140 E - Palindrome-less Arrays的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。