近期 AtCoder Beginner Contest 题目选做

RB16B / 2023-07-16 / 原文

AtCoder Beginner Contest 310 E

https://atcoder.jp/contests/abc310/tasks/abc310_e

我们要求所有区间的 NAND 之和，发现 NAND 最后只可能是 \(0\) 或 \(1\)，所以我们只需要计数区间 NAND 为 \(1\) 的即可。

考虑 dp，设 \(f_{i,0/1}\) 表示以 \(i\) 结尾的区间最后 NAND 和为 \(0/1\) 的方案数。

然后就是随便做做：

\[f_{i + 1,1} \leftarrow f_{i,0}+[A_{i+1}=0]f_{i,1}+[A_{i+1}=1] \]

\[f_{i + 1, 0} \leftarrow [A_{i+1}=1]f_{i,1}+[A_{i+1}=0] \]

边界条件 \(f_{1,A_1} = 1, f_{1,1-A_1}=0\)。

最后答案就是 \(\displaystyle \sum_{i = 1}^{n} f_{i,1}\)。

记得开 long long。

https://atcoder.jp/contests/abc310/submissions/43640127

AtCoder Beginner Contest 310 F

https://atcoder.jp/contests/abc310/tasks/abc310_f

很一眼，考虑 dp。

只要求求出和为 \(10\) 的方案，那可以很暴力，干脆就状压，看选出的方案能组成 \(0\sim 10\) 的那些数。

设 \(f_{i,S}\) 表示目前考虑到第 \(i\) 个骰子，可以得到 \(S\) 中的所有数（\(0 \sim 10\) 之间）。

然后就是枚举一下第 \(i\) 个骰子出来的值，如果在 \([1, 10]\) 之间就枚举，否则就批量处理。

转移啥的就是模拟了，注意不要算重了，具体见代码。

https://atcoder.jp/contests/abc310/submissions/43629988

AtCoder Beginner Contest 310 G

https://atcoder.jp/contests/abc310/tasks/abc310_g

不太好想，看到 \(K\) 是 \(10^{18}\) 量级的，所以考虑倍增。

差不多是快速幂的思路，如果二进制里有一个 \(1\) 就做一次单独的操作。

然后就是当前的球数做一次操作再自加，\(A\) 数组按 \(A\) 数组操作一遍，差不多就是快速幂里的自己乘自己。

最后别忘了处理一下有没有算第 \(K\) 次操作，有没有减去初始局面。

算 \(K^{-1}\) 的时候别忘了先对 \(K\) 取一个模。

https://atcoder.jp/contests/abc310/submissions/43658994