AT_arc059_d バイナリハック

题解区什么鬼。

只讲转移不说意义吗。这个真的很显然吗。

不妨考虑先钦定操作序列（敲字符还是退格），再钦定具体敲了哪个键。

首先，考虑这一个点，如果一个字符最终被删掉了，那么这个字符是 是 其实无所谓。如果一个字符最终被保留了下来，那么这个字符就必须是对应位置上的字符。

换句话说，假设敲了 个没有被退掉的字符， 个被退格键退掉了，那么总共的敲键方案数就是 。原因每个是 个被退掉的字符都有 种选择，而 个字符只能选择字符串对应位置上的字符。并且每个位置的选择是独立的。

因此，我们只需要对于每个合法的操作序列（ 个有效字符，总敲击次数为 ），都像这样计算贡献即可。

可以考虑 DP。但是，如果要记录有几个键被退掉了，那么则不能很好的设计状态 DP。

考虑一个延迟决策的思想，我们一开始让每个键都是正常键，等到一个字符被退格退掉的时候，我们再将其贡献 。此时我们只需要记录敲击次数和字符串长度即可。

具体地，考虑 表示前 次敲击敲出来了 个有效字符的方案数。转移如下。

• 敲退格。
  • ，退格是空敲。转移到 。
  • ，退掉了一个有效字符，那么那个字符就可以随意选择敲 了。 转移到 。
• 敲字符。转移到 。

复杂度平方。