传送门
如果观察到性质其实也不是很难想。
然而考试的时候慌得一批只有心思写暴力233.
下面是几个很有用的性质：
- c0,1+1≥c1,0≥c0,1c_{0,1 }+1 ≥ c_{1,0} ≥ c_{0,1}c0,1+1≥c1,0≥c0,1，因为$ 10, 01 $是交替出现的。
- c1,0+c0,0c_{1,0 }+c_{0,0}c1,0+c0,0是000出现的次数。
- c0,1+c1,1+1c_{0,1}+ c_{1,1}+1c0,1+c1,1+1 是111 出现的次数。
由于满足条件的数一定是一段111，一段000，一段1...1...1...
因此我们可以利用性质一算出0/10/10/1的段数。
然后性质二三可以告诉我们0/10/10/1出现的次数。
这样就可以用数位dpdpdp+组合数转移了。
代码