设\(f_{i,0}\)表示将\([1,i]\)位变成以\(0\)结尾的字符串的最小步数。
\(f_{i,1}\)表示将\([1,i]\)位变成以\(1\)结尾的字符串的最小步数。
\(f_{i,2}\)表示将\([1,i]\)位变成空字符串的最小步数。
转移的时候分类讨论一下第\(i\)位的选取与否，注意要求方案数，所以要注意分讨的不重不漏。
比如：\(s_i=0\)的情况。
以\(0\)结尾，讨论\(s_i\)删与不删，\(f_{i,0}\leftarrow min\{f_{i-1,0}+1,f_{i-1,1},f_{i-1,2}\}\)。
以\(1\)结尾，讨论\(s_i\)删与不删，因为\(s_i=0\)，所以一定要删，删了之后就是\(i-1\)的情况，\(f_{i,1}\leftarrow f_{i-1,1}\)。
空串，全部都要删掉，第\(i\)个一定要删，\(f_{i,2}\leftarrow f_{i-1,2}+1\)。
\(s_i=1\)类似。
初始时，\(f_{0,0}=f_{0,1}=+\infty,f_{0,2}=0\)。
不难发现，上述的每次分类都是不重不漏的，\(g\)数组表示方案，一样维护。
\(g_{0,0}=g_{0,1}=0,g_{0,2}=1\)。
然后发现\(g\)表示的方案是有序的，因为动态规划的时候是从前往后，删的数肯定也是从前往后的。
所以乘上\(ans!\)即可。
需要注意，每个CASE都memset整个数组，会TLE，所以清空\(n\)的长度就行了（循环，memset都行）。
题解大部分都是组合数学的做法。
显然，连续的一段\(1\)或者\(0\)，必须要变成1个\(0\)或者\(1\)。
比如有连续\(k\)个1，就要删掉\(k-1\)个，但是具体怎么删呢？就是从\(k\)个里面选\(k-1\)个数。
然后发现选择的方案是有序的，但是如果你直接算\(k!\)，方案就会把这些成段的删除的数绑定在一起，就错误了。
所以直接算组合数，最后把选出来的数乘上\(ans!\)即可。
标签：Alternating,方案,CF1879C,结尾,leftarrow,Make,字符串,步数,不删 From： https://www.cnblogs.com/zhangchenxin/p/17799897.html