CodeForces 1140E Palindrome-less Arrays ``标签真好用。但要是vj挂了，我这里的题面也挂了…… Time limit 2000 ms <p>Memory limit 262144 kB</p> <p>Source Educational Codeforces Round 62 (Rated for Div. 2)</p> <p>Tags combinatorics dp *2200</p> <p>Editorial <a href="http://codeforces.com/blog/entry/66084" target="_blank">Announcement #1 (en)</a><a href="http://codeforces.com/blog/entry/66084" target="_blank">Announcement #2 (ru)</a> <a href="http://codeforces.com/blog/entry/66147" target="_blank">Tutorial #1 (en)</a> <a href="http://codeforces.com/blog/entry/66147" target="_blank">Tutorial #2 (ru)</a></p> <h2 id="中文题意">中文题意</h2> <p>给一个长度为n的序列，其中的数字范围是[1,k]，有一些已经给定了，另一些空着等我们填数字（用-1表示）。我们要在所有空着的地方填入[1,k]范围内的整数，并且使填完后的序列里没有长度为奇数的回文串(单个不算)。问总的方案数%998244353。<s>993244853</s></p> <h2 id="解题思路">解题思路</h2> <p>看到这题，先瞪着草稿纸思考一波……奇数的回文串一定会有一个“中心”，往两边走依次相等，那么不满足题意的条件就是，至少有一个中心<span class="math inline">(a_i)</span>，相邻两边的数字<span class="math inline">(a_{i-1})</span>和<span class="math inline">(a_{i+1})</span>相等。所以，我们可以用总的方案数减去不满足要求的方案数。但……想了几种计算不满足的方案数的方法，都做不到不重不漏，弃疗，看题解——</p> <p>直接算就好，不用减。要求的是有多少种填数方式，使所有<span class="math inline">(a_{i-1})</span>和<span class="math inline">(a_{i+1})</span>不相等，然后可以想到(<s>我就想不到</s>)，序列的奇数项和偶数项可以分开计算，互不干扰，最后把两个的答案相乘就好。对于分开后的每个子序列，只用让序列中没有相邻两项就好。有没有一点眼熟<a href="https://www.luogu.org/problemnew/show/P3197" target="_blank">HNOI2008 越狱</a>。</p> <p>当给的序列里只有-1，也就是全部要我们自己填时，差不多就是“越狱”了。当序列里有一些给定的值时，这些给定值就会把连续的-1序列切断成几节。因为我们只需要让序列中相邻项不相等，所以每一节-1串之间不会互相影响，只用单独处理每个-1串，再把它们的方案数乘起来就好。</p> <p>对于每一个长度为len的-1子串，可以分以下几种情况</p> <ul> <li>两边都没有给定数字存在，这个不叫子串了，也就是“越狱”了。 <ul> <li>答案就是“越狱”那题的<span class="math inline">(k*(k-1)^{len-1})</span></li> </ul> </li> <li>单边没有给定数字，也就是左边或者右边就是序列外面了。 <ul> <li>思路类似“越狱”，可以得到，答案是<span class="math inline">((k-1)^{len})</span></li> </ul> </li> <li>两边的给定数字不相等 <ul> <li>这种子串的方案数量用<span class="math inline">(dp[len][0])</span>表示</li> </ul> </li> <li>两边的给定数字相等 <ul> <li>这种子串的方案数量用<span class="math inline">(dp[len][1])</span>表示</li> </ul> </li> </ul> <p>先思考边界，只有一个-1时比较显然，只用看这个-1的两边就好，<span class="math inline">(dp[1][0]=k-2)</span>，<span class="math inline">(dp[1][1]=k-1)</span>。</p> <p>然后开始转移（下面的<span class="math inline">(len>1)</span>）——</p> <ul> <li>用△▽□表示不相等的给定数字。用****表示某个长度的-1串</li> <li>对于<span class="math inline">(dp[len][1])</span>，可以表示成△****△。我们先把边上的一个-1固定下来——△***▽△。由于和右边的△相邻，所以▽不能和△相等，所以▽有<span class="math inline">(k-1)</span>种选择，于是问题转化成△****▽。所以，$$dp[len][1]=dp[len-1][0]*(k-1)$$。</li> <li>对于<span class="math inline">(dp[len][0])</span>，同样可以先固定一个边上的-1——△***□▽。然后对□分类 <ul> <li>当□=△时，方案数是<span class="math inline">(dp[len-1][1])</span>。</li> <li>当□!=△时，□!=▽，所以方框只有<span class="math inline">(k-2)</span>种选择，这种情况方案数是<span class="math inline">(dp[len-1][0]*(k-1))</span>。</li> </ul> </li> <li>上面两种情况相加可得<span class="math inline">(dp[len][0]=dp[len-1][1]+dp[len-1][0]*(k-1))</span>。</li> </ul> <p>然后因为我们这里处理的都只是原序列的一半，所以<span class="math inline">(lenleqslantfrac{n}{2})</span>。</p> <p>总结一下就是，先读入n，预处理出dp数组。在输入序列的时候把原序列分成奇偶两个子序列。对于每个子序列，先计算两边的-1串(如果有)，再计算中间的-1串。顺便，给定的数字，多判断一下它们和相邻的是否相等，完事。</p> <h2 id="源代码">源代码</h2> <pre><code class="language-cpp">#include<stdio.h> #define mod 998244353 long long n,s[2][100010],k; long long dp[100010][2]; long long ans=1; long long p(long long a,long long b) { if(b==0) return 1LL; if(b==1) return a%mod; long long x=p(a,b>>1); x*=x; x%=mod; x*=p(a,b&1); x%=mod; return x; } void solve(long long *a,long long len) { long long l,r; l=0; while(!(~a[l])&&a[l]) l++;//处理左边的-1串 if(l==len+1) { ans=ans*k%mod*p(k-1,len)%mod;//全是-1串 return; } ans*=p(k-1,l); ans%=mod; r=len; while(r>=0&&!(~a[r])) r--;//处理右边的-1串 if(r<len) ans*=p(k-1,len-r),ans%=mod; r++; for(int i=l,count=0;i<=r;i++) { if(a[i]==-1)//统计中部-1串的数量 { count++; continue; } else if(count)//计算中间的-1串 { if(a[i]==a[i-count-1]) ans*=dp[count][1]; else ans*=dp[count][0]; ans%=mod; count=0; } else if(i&&a[i]==a[i-1])//给定数字中，相邻的相同 { ans=0; return; } } return; } int main() { //freopen("test.in","r",stdin); scanf("%lld%lld",&n,&k); for(int i=0;i<n;i++) scanf("%lld",&s[i&1][i>>1]); dp[1][0]=k-2;dp[1][1]=k-1; for(int i=2;i<=n>>1;i++) { dp[i][0]=dp[i-1][1]+dp[i-1][0]*(k-2)%mod; dp[i][1]=dp[i-1][0]*(k-1)%mod; dp[i][0]%=mod; dp[i][1]%=mod; } solve(s[0],n-1>>1); if(!ans) { puts("0"); return 0; } solve(s[1],(n-1>>1)-(n&1)); printf("%lld ",ans); return 0; } </code></pre>