Educational Codeforces Round 120

D

D. Shuffle
题目大意，给定一个 0101 串，要求找到恰好包含 kk 个 11 的连续子串，然后任意打乱子串顺序
一次操作之后，可以得到多少个不同的串？

对于区间 [l,r][l, r] 任排，考虑能够得到多少个 0101 串，记区间中 11 的个数为 c1c_1，很明显答案是 (r−l+1c1)\displaystyle\binom{r-l+1}{c_1}

如果枚举每一个位置 [l,r][l, r] 都这样算的话，很明显有重复计算，假设 [l′,r′]⊂[l,r][l', r'] \subset [l, r]
那么对 [l′,r′][l', r'] 统计任排方案的时候，在计算 [l,r][l, r] 的时候又被统计了一遍
edu120d

实际上，考虑如何计算 [l,r][l, r] 区间的排列方案数，假设区间 [l,r][l, r] 中有 c1c_1 个 11，考虑其子区间 [l′,r′][l', r']

S([l,r] 方案数)=S([l′,r′] 任排，[l,l′−1]∪[r′+1,r] 不变)+S([l′,r′] 任排，[l,l′−1]∪[r′+1,r] 改变)\begin{aligned}S([l, r] \ \text{方案数}) &= S([l', r'] \ \text{任排，}[l,l'-1] \cup [r'+1, r] \ \text{不变}) \\ &+ S([l', r'] \ \text{任排，}[l, l'-1] \cup [r'+1, r] \ \text{改变}) \end{aligned}

注意到，S([l′,r′] 任排，[l,l′−1]∪[r′+1,r] 不变)S([l', r'] \ \text{任排，}[l,l'-1] \cup [r'+1, r] \ \text{不变}) 的方案数，实际上是

(r′−l′+1c1′)\displaystyle\binom{r'-l'+1}{c_1'}，c1′c_1' 为 [l′,r′][l', r'] 区间中 11 的个数

难点在于如何计算 [l,l′−1]∪[r′+1,r][l, l'-1] \cup [r'+1, r] 一定发生改变的方案数？
不妨令 pl′<l′, pr′>r′pl' < l', \ pr' > r'，可以考虑如下做法

枚举区间 [l′,r′][l', r'] 外侧发生改变的位置，即枚举 [pl′,pr′][pl', pr']，其中 pl′pl' 是左边最外侧发生改变的位置
即 pl′−1→lpl'-1 \to l 都不变，pl′pl' 一定改变，pr′pr' 同理，将枚举计算出的答案加起来就可以了

这样的结构，可以考虑用递推，枚举发生改变的位置 pl′,pr′pl', pr'，然后递推到更大的区间
具体来说，每一次枚举发生改变的区间 [l,r][l, r]，其中 l,rl, r 端点一定是会发生改变的，[l+1,r−1][l+1, r-1] 子区间任排
算法实现
枚举 ll，对于每个 ll，先令 [l,r]←[l,l+1][l, r] \leftarrow [l, l+1]（一开始令区间长度最小）
然后递推计算 ([l,r]→[l,r+1]→[l,r+2]⋯[l,n])\left([l, r] \to [l, r+1] \to [l, r+2] \cdots [l, n]\right)，这样对于每一个 ll
我们都枚举了每个可能发生改变的右端点，将答案加起来，就得到了 ll 的贡献
把每一个 ll 的贡献加起来，就是总贡献

计算 [l,r][l, r] 对答案的贡献也很简单，对于 [l,r][l, r] 区间，l,rl, r 位置的值一定和原串不同
这样我们就知道了 [l+1,r−1][l+1, r-1] 子区间有多少个 11，假设为 c1c_1，那么这个区间的贡献就是 (r−l−1c1)\displaystyle\binom{r-l-1}{c_1}

最后不要忘了把答案 +1+1，即对原串不做任何修改的方案

计数问题杂题