比赛地址

怪文書 / Dubious Document

算一下每个字符的最少出现次数即可。

代码

井井井 / ### 

考虑每个小矩形的贡献,可以得到

$$ \sum_{i=1}^{n-1}\sum_{j=1}^{m-1}i(n-i)j(m-j)(x_{i+1}-x_i)(y_{j+1}-y_j) $$

$$ \left(\sum_{i=1}^{n-1}i(n-i)(x_{i+1}-x_i)\right)\times\left(\sum_{j=1}^{m-1}j(m-j)(y_{j+1}-y_j)\right) $$

直接计算即可。

TrBBnsformBBtion

先给出结论:把 A 看成 $1$、B 看成 $2$,那么一个串能变成另一个串当且仅当两个串的和在模 $3$ 意义下相等。下面是证明。

先证必要性。如果把 A 变成 BB,则和增加了 $3$;如果把 B 变成 AA,则和不变;如果把 AAABBB 删去,则和减少 $3$ 或 $6$。于是一次操作前后和模 $3$ 的值不变,从而任意次操作前后和模 $3$ 的值都不变。

再证充分性。首先可以发现操作是可逆的:BB -> AAAA -> AA -> BB -> AAAAA -> BB -> AAB -> ABBBA -> BB -> BAA -> BBBA。另外,通过 B->AAAAAA -> A,我们可以把任意一个串变成 AAAAAA 中的一个。因为这 $3$ 个串的和 $\bmod 3$ 各不相同,所以两个和 $\bmod 3$ 相同的串可以变成同一个串,从而一个串可以变成另一个串。

这样子我们就证明了和 $\bmod 3$ 相同是充要条件,对两个串求个前缀和即可。

代码

Infinite Sequence

首先可以发现,如果两个 $>1$ 的数相邻,那么后面唯一确定。

设 $dp_i$ 表示 $[i,n]$ 的方案数。转移时分类讨论:

  • 如果 $i$ 填了 $1$:方案数为 $dp_{i+1}$。
  • 如果 $i$ 没有填 $1$、$i+1$ 也没有填 $1$:方案数为 $(n-1)^2$。
  • 如果 $i$ 没有填 $1$、$i+1$ 往后的一段填了 $1$:$i+a_n\leq n$ 的方案数为 $\sum_{j=i+3}^n dp_j$;$i+a_n>n$ 的方案数为 $i+1$。

后缀和优化转移即可。边界是 $dp_n=n,dp_{n-1}=n^2$。

代码

最后修改:2020 年 09 月 17 日 04 : 41 PM