[CTSC2016]萨菲克斯·阿瑞()

完全不想做题,所以跑去叮飘飘蛋(因为苍蝇不叮无缝蛋)。

顺便看到了这题,然后我就成了蛋神的小黄鸭。然后我就把我知道的写下来了。

所以,没错,这又是在口胡了。口胡是愚蠢的做法,毫无疑问。

由于我博客园上随笔的风格都偏向于 \(\rm manuscript\),就不分子标题了。

感觉用分割线还是挺舒服的。这是咋整的啊?

考虑怎么判定某个 \(sa\) 合法。显然只用考虑相邻元素 \(i,j\) 。显然通过 \((i{+}1),(j{+}1)\) 在 \(sa\) 中的前后关系可以确定字符 \(s_i<s_j\) 或 \(s_i\leqslant s_j\) 。而且该条件是充要的。

因此一个 \(sa\) 可以唯一生成一个不等式链,其中含有 \(<\) 和 \(\leqslant\) 。

但不同不等式链不对应不同 \(sa\),即某些不等式链不会被生成。否定词最多的一句话。

从题目要求中,可以想到一个更好的对应是,取该不等式链的最小解,即 \(\leqslant\) 连接的字符都相同,用 \(<\) 连接的同字符块连续递增。不妨令这些字符为从小到大的自然数。

此时一个 \(sa\) 可以唯一生成一个字符串,该字符串的字符集大小为 \(sa\) 生成的不等式链中 \(<\) 的数量加一。显然每个字符串至多可被一个 \(sa\) 生成,那就是它拥有的 \(sa\) 。

考虑计数。显然我们想要计数表示方式。从一个简单的例子入手。设此种 \(sa\) 的唯一生成字符串中有 \(a\) 个 ,\(b\) 个 ,\(c\) 个 ,则多重组合数 \({a+b+c\choose a,\;b,\;c}\) 肯定不会算漏。但是可能会多算。

1
2
3

考虑某个此种字符串 \(\tilde S\) 所拥有的 \(sa\) 。若该 \(sa\) 的生成字符串非 \(\tilde S\),则其被错误地统计了。生成字符串与不等式链挂钩;该 \(sa\) 的生成不等式链,我们希望是

这样该 \(sa\) 就会生成 \(\tilde S\) 。而其他的可能的情况,显然是 \(<\) 变为 \(\leqslant\),比如

这样该 \(sa\) 就不会生成 \(\tilde S\) 。它会生成有 \((a{+}b)\) 个 和 \(c\) 个 的字符串。

1
2

另一方面,生成字符串中含有 \((a{+}b)\) 个 和 \(c\) 个 的 \(sa\) 总是会被错误地统计恰好一次(通过查看其不等式链,容易找到使其被统计的 \({a+b+c\choose a,\;b,\;c}\) 类串)。

1
2

因此,我们计算的 \({a+b+c\choose a,b,c}\) 就是所有 \(<\) 可以被自由替换为 \(\leqslant\) 的总 \(sa\) 数量。于是容斥得到

这就是真正的 \(sa\) 的数量。

然而原题中给出了每种字符的限制。因此一种字符用完后,会开始使用下一个字符。相当于将两个字符合并起来了。

枚举字符怎样合并。显然,若干合并的字符中,只有最大的一个可能未用尽。因为填字符是个贪心的过程。

然后容斥的过程是枚举“段”怎样合并,最后的贡献是二项式系数与符号。

这是在字符种类上很连续的,考虑 \(\tt dp\) 。设 \(f_i(j,k)\) 表示已经考虑了前 \(i\) 种字符,填了 \(j\) 个位置,末尾有个长为 \(k\) 的段准备合并,所有方案的容斥系数和。转移比较简单:

  • 该种字符是段的末尾,并且不与后一个段合并。
  • 该种字符是段的末尾,但是与后一个段合并。注意段的合并有容斥系数。
  • 该种字符不是段的末尾,则其必须用尽。

注意上面每个字符都是被使用的,所以真实答案需枚举有多少个字符被使用,即 \(ans=n!\sum_{i=1}^mf_i(n,0)\),前面的 \(n!\) 是补全二项式系数。

最后前缀和优化转移,时间复杂度 \(\mathcal O(n^2m)\) 。

此时距离飘飘蛋切掉此题已经过去 \(21\textrm{h}\) 了。这就是差距吧。

————————

完全不想做题,所以跑去叮飘飘蛋(因为苍蝇不叮无缝蛋)。

顺便看到了这题,然后我就成了蛋神的小黄鸭。然后我就把我知道的写下来了。

所以,没错,这又是在口胡了。口胡是愚蠢的做法,毫无疑问。

由于我博客园上随笔的风格都偏向于 \(\rm manuscript\),就不分子标题了。

感觉用分割线还是挺舒服的。这是咋整的啊?

考虑怎么判定某个 \(sa\) 合法。显然只用考虑相邻元素 \(i,j\) 。显然通过 \((i{+}1),(j{+}1)\) 在 \(sa\) 中的前后关系可以确定字符 \(s_i<s_j\) 或 \(s_i\leqslant s_j\) 。而且该条件是充要的。

因此一个 \(sa\) 可以唯一生成一个不等式链,其中含有 \(<\) 和 \(\leqslant\) 。

但不同不等式链不对应不同 \(sa\),即某些不等式链不会被生成。否定词最多的一句话。

从题目要求中,可以想到一个更好的对应是,取该不等式链的最小解,即 \(\leqslant\) 连接的字符都相同,用 \(<\) 连接的同字符块连续递增。不妨令这些字符为从小到大的自然数。

此时一个 \(sa\) 可以唯一生成一个字符串,该字符串的字符集大小为 \(sa\) 生成的不等式链中 \(<\) 的数量加一。显然每个字符串至多可被一个 \(sa\) 生成,那就是它拥有的 \(sa\) 。

考虑计数。显然我们想要计数表示方式。从一个简单的例子入手。设此种 \(sa\) 的唯一生成字符串中有 \(a\) 个 ,\(b\) 个 ,\(c\) 个 ,则多重组合数 \({a+b+c\choose a,\;b,\;c}\) 肯定不会算漏。但是可能会多算。

1
2
3

考虑某个此种字符串 \(\tilde S\) 所拥有的 \(sa\) 。若该 \(sa\) 的生成字符串非 \(\tilde S\),则其被错误地统计了。生成字符串与不等式链挂钩;该 \(sa\) 的生成不等式链,我们希望是

这样该 \(sa\) 就会生成 \(\tilde S\) 。而其他的可能的情况,显然是 \(<\) 变为 \(\leqslant\),比如

这样该 \(sa\) 就不会生成 \(\tilde S\) 。它会生成有 \((a{+}b)\) 个 和 \(c\) 个 的字符串。

1
2

另一方面,生成字符串中含有 \((a{+}b)\) 个 和 \(c\) 个 的 \(sa\) 总是会被错误地统计恰好一次(通过查看其不等式链,容易找到使其被统计的 \({a+b+c\choose a,\;b,\;c}\) 类串)。

1
2

因此,我们计算的 \({a+b+c\choose a,b,c}\) 就是所有 \(<\) 可以被自由替换为 \(\leqslant\) 的总 \(sa\) 数量。于是容斥得到

这就是真正的 \(sa\) 的数量。

然而原题中给出了每种字符的限制。因此一种字符用完后,会开始使用下一个字符。相当于将两个字符合并起来了。

枚举字符怎样合并。显然,若干合并的字符中,只有最大的一个可能未用尽。因为填字符是个贪心的过程。

然后容斥的过程是枚举“段”怎样合并,最后的贡献是二项式系数与符号。

这是在字符种类上很连续的,考虑 \(\tt dp\) 。设 \(f_i(j,k)\) 表示已经考虑了前 \(i\) 种字符,填了 \(j\) 个位置,末尾有个长为 \(k\) 的段准备合并,所有方案的容斥系数和。转移比较简单:

  • 该种字符是段的末尾,并且不与后一个段合并。
  • 该种字符是段的末尾,但是与后一个段合并。注意段的合并有容斥系数。
  • 该种字符不是段的末尾,则其必须用尽。

注意上面每个字符都是被使用的,所以真实答案需枚举有多少个字符被使用,即 \(ans=n!\sum_{i=1}^mf_i(n,0)\),前面的 \(n!\) 是补全二项式系数。

最后前缀和优化转移,时间复杂度 \(\mathcal O(n^2m)\) 。

此时距离飘飘蛋切掉此题已经过去 \(21\textrm{h}\) 了。这就是差距吧。