ARC133

· · 个人记录

A

想了好半天。

只用关心每个字符的第一次出现，后面显然。

B

直接 f_{i,j}，树状数组优化一下转移。

C

首先先把有无解判了： \sum a_i\equiv \sum b_i(\bmod k)

否则先把每个位置都打满成 k-1，然后记 a'_i 表示第 i 行至少要减去多少，b'_i 类似。

然后看起来最少需要减的就是 \max(\sum a_i,\sum b_i)，写一发发现过了，正确性用贪心证明应该也是不难的。

D

根据前缀异或和的经典结论，大概就是讨论 l-1 和 r 模 4 的余数分开统计。

当然这属于纯纯的口胡，光有这句话我完全不知道怎么写，所以细说一下转化流程。

首先利用容斥把问题转化成标准形式 \sum_{i=0}^n\sum_{j=0}^m[i\oplus j=k]。

然后枚举 i,j 模 4 的余数，保证后两位异或出来是对的，统计前面的数位可以取 0 到多少。然后转化成如下标准形式：

统计：\sum_{i=0}^n \sum_{j=0}^m[g(i)\oplus h(j)=k]，其中 g,h 为函数 f(x)=0 或 f(x)=x。

如果两个都是 f(x)=x 则简单数位 dp 求解，否则直接计算。

代码：https://atcoder.jp/contests/arc133/submissions/41465553

E

较为常规的计数题。

首先肯定转化成对每个 i 统计答案大于等于 i 的个数，然后转成一个 bool 变量相关的问题。

然后就是倒推，尝试分析在倒数某次操作确定答案的情况对应的方案数。

发现困难麻了，但是这个 01 赋值的形式有个经典套路就是收尾配对，即对于 i 在第 s 步确定为 1 的方案数等于对于 k-i 在第 s 步确定为 0 的方案数，于是就不用枚举 s 了，对于所有在运行到 A 前结束的方案，两者加起来恰好有一半是 0 另一半是 1。

现在变成只用对 i 统计能运行到 A 那里的方案数，这个按照 gcd(n,m) 随便讨论一下就行了。

代码应该难度不大，不想写了，直接贺了。

F

不会。明天争取更

我声称我学会了，但是反正学会了下一道还是不会，而且打公式太累了，所以题解就咕了。