CF-1140 E - Palindrome-less Arrays

题意：给定一个没有填完的序列，数值为-1表示你可以用 1~k 中的数字去覆盖它，求将该序列填充后，不存在长度为奇数的回文串的方案数

分析：

使之不存在长度为奇数的回文串，只需要满足不存在长度为3的回文串即可。换句话说：\(a[i] \neq a[i+2]\) 对所有的 \(i\) 成立。可以发现 i 为奇数与 i 为偶数是互不影响的。所以可以把它划分为两个串

一个串由 $a_1,a_3,a_5, \dots $组成

另一个串由$ a_2,a_4,a_6,\dots$ 组成

现在问题转化为了：给定一个序列，将其数值为-1的位置换为1~k中的数字，使得序列中两两相邻数字不同的方案数。不妨换个角度想，任何一组连续的 -1（长度可以为0或1），两边都只有四种情况

两边都没有数字（即整个串都是-1）

两边中有一边没有没有（只有整个串的左右两端有这种情况）

两边的数字相同

两边的数字不同

另外我们可以发现，前两种情况可以由后两种情况推出来，所以只需预处理把 0~ (n/2)+1长度的-1串的方案数都预处理出来，问题就迎刃而解了。

设\(d(i,j)\) 表示长度为 \(i\) 的 -1 串，j 为0 表示两边数字相同，为1表示两边数字不同时的方案数，\(d[0][0] = 0, d[0][1] = 1\), 有转移方程：

• \(i\) 为奇数
  • \(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\) 为偶数
  • \(d[i][0] = (k-1)*d[i-1][1]\)
  • \(d[i][1] = d[i-1][0] + (k-2)*d[i-1][1]%mod\)

对于 i 为奇数的情况，我们可以取出这个序列的中间位置 mid，当 -1 串两端数字相同且都等于 x 时，先假设mid数字与x相同，那就转换为了两个长度为 i/2，序列两端相同 的子问题，然后假设 mid 与 x不同，那么就有(k-1)种方法，可以同样转换成两个长度为 i/2 ，序列两端不同的子问题。当 -1 串两端数字不同时，同理。

预处理d数组之后，就可以对我们之前分好的奇偶串做处理了。思路就是记录上一个不为-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; }

转载于:https://www.cnblogs.com/1625--H/p/10660923.html

总结

以上是生活随笔为你收集整理的CF-1140 E - Palindrome-less Arrays的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。