Orz qwaszx！

A. 循环

来源：原创

众所周知：

$\frac{1}{7}=0.142857...$

$\frac{2}{7}=0.285714...$

$\frac{3}{7}=0.428571...$

$\frac{4}{7}=0.571428...$

$\frac{5}{7}=0.714285...$

$\frac{6}{7}=0.857142...$

为什么？仅仅是因为 $7​$ 这个数很神奇？

事实上，该性质并非 $7$ 独有。

$17,19,23,29,47$，包括 $786433$ 等数具有相同的性质——循环节彼此可以通过循环移位得到。

而对于 $13$ 而言，循环节均为 $6$ 位，分子为 $1,3,4,9,11,12$ 的和 $2,5,6,7,8,11$ 的分别具有上述性质。

我们发现，$\gcd(x,p)=\gcd(10x \mod p,p)$，且 $\frac{10x \mod p}{p}$ 的一个循环节由 $\frac{x}{p}$ 的循环节循环左移一位得到。

而根据价值的定义，这两个小数价值相等。

再考虑一下作除法的过程：要计算 $\frac{x}{p}$，先令 $x\leftarrow 10x$，再将 $x$ 除以 $p$ 的商写下来作为商的这一位，然后令 $x\leftarrow x \mod p$，再进行下一位的除法。当当前的 $x$ 与初始的 $x$ 相同时，就找到了一个循环节。

那么实际上 $x$ 在这个过程中的变化轨迹是，每次 $x\leftarrow 10x \mod p$，而变化轨迹中取到的所有 $x$，价值都与初始的 $x$ 价值相等！

根据一些基本的数论知识，我们知道这种变化轨迹把 $[1,p-1]$ 内的整数划分成若干个环。即不可能从两个不在同一轨迹内的 $x$ 开始变到同一个数。

那么相当于，我们用变化轨迹长度的时间算出了变化轨迹长度个 $x$ 的答案，均摊下来算一个的复杂度是 $O(1)$！

于是我们只需要每次找出一个没计算的数，暴力计算一次，并把变化轨迹内所有数标为已计算。

复杂度瓶颈在于：维护一个集合，每次删去一个数，或随便找出一个还在集合内的数。视实现 $O(p)$ 或 $O(p\alpha(p))$ 或 $O(p\log p)$.

标程使用 std::set 实现，跑了 1.2s 多，但考虑到有更好的实现方式，故时限开了 2s.

B. 博弈

来源：LOJ #3193

考虑优化暴力 DP。

打表发现，对于大部分的 $(i,j)$ 都有 $F(i,j)=F(i+1,j+1)$. 具体地来说，若 $(i,j),(i+1,j),(i+2,j),(i+1,j+1),(i,j+1),(i,j+2)$ 这 $6$ 个格子都没有球洞或边界，那么 $F(i,j)=F(i+1,j+1)$. 这是因为先后手都能达到这个界：后手无论如何都能移到 $(i+1,j+1)$；假设先手在 $(i+1,j+1)$ 的最优策略是移到 $(i+1,j+2)$, 那么这一步可以移到 $(i,j+1)$, 否则移到 $(i+1,j)$.

于是对于一个有球洞的位置 $(x,y)$ , 可以将它影响的 $6$ 个位置设为需要特殊处理的位置。我们定义 $x−y$ 为常数的点构成的集合为“正对角线”，$x+y$ 为常数的点构成的集合为“反对角线”，那么同一条正对角线上一定会被需要特殊处理的格子分成若干段，其中每段 $F$ 值均相等。那么我们的目标就是求出每个特殊点的 $F$ 值，然后答案就等于每个特殊点的 $F$ 值乘以段长之和。考虑按所在反对角线从大往小的顺序处理所有需要特殊处理的格子（即把所有特殊点按 $x+y$ 排序），顺便用 map 维护每条正对角线上格子的 $F$ 值即可。

时间复杂度 $O(K\log K)$, 可以通过所有子任务，期望得分 $100$ 分。

C. 数据结构

来源：模拟赛题。

由于我太菜，严重高估了本题的难度，十分抱歉/kk

本题有很多做法，下面讲最简单（？）的一种：

这题看上去不太能 $\text{polylog}$，于是我们期望获得一个根号复杂度的算法。

考虑按串中 0 和 1 的个数分治。把所有修改串分成两种：1 的个数 $\ge \frac{n}{2}$ 的（称为 A 部）和 $\lt \frac{n}{2}$ 的（称为 B 部）。在修改时我们很容易在 $O(2^{\frac{n}{2}})$ 的时间复杂度内维护出 A 部的子集和和 B 部的超集和。

现在考虑询问：如果 ? 的个数不超过 $\frac{n}{2}$，那么最简单有效的办法显然是暴力枚举所有的 ?. 否则，0 和 1 的个数都不超过 $\frac{n}{2}$，我们需要分别统计两部分的贡献。对于 A 部，我们知道所有的子集和，可以暴力枚举所有的 1，通过容斥替换成 0 和 ?; B 部同理，知道所有的超集和，暴力枚举所有的 0，通过容斥替换成 1 和 ?. 这样询问的总复杂度是 $O(2^{cnt_0}+2^{cnt_1})\le O(2^{\frac{n}{2}})$.

总时间复杂度 $O(q2^{\frac{n}{2}})$.

值得注意的是，这题虽然有很多复杂度正确的算法，但是按串的前一半后一半分治的算法很容易跑满，因此实际表现远不如按字符个数分治的算法。