ABC448 数论分治|莫队分块构造

E题

题意非常简单，一个大到无法正常读入的N，还有一个M，需要求$\lfloor N/M\rfloor$除以10007的余数

首先，一个非常经典的观察
$$\lfloor \frac{N}{M}\rfloor \mathrm{mod}10007=\lfloor \frac{N\mathrm{mod}(10007M)}{M}\rfloor$$

首先，我们要先处理一下这个输入的游程编码，现在假设输入的是 $c$，连续出现 $l$ 次，假设现在已经处理完的数是$a $，那么我们要在它后面加上一段长度为 $l$ 的 $c$ ，因此只需要让
$$a\cdot 10^l+c\cdot R_l(\mathrm{mod}10007M)$$
其中
$$R_l=111\cdots 1(\mathrm{mod}P)$$
至此我们已经完成很多了，接下来我们只需要求$10^l$和$R_l$

如果说是偶数长$l=2t$

那么$R_t$也就是前面 $t$ 个1，后面 $t$ 个1，其实也就是$R_t\cdot 10^t+R_t$

而
$$\begin{gathered} 10^{2t}=(10^t{)}^2 \\ {R}_{2t}=R_t\cdot 10^t+R_t=R_t(10^t+1) \end{gathered}$$
又如果是奇数长$l=2t+1$
$$\begin{gathered} 10^{2t+1}=10^{2t}\cdot 10 \\ {R}_{2t+1}=R_{2t}\cdot 10+1 \end{gathered}$$
$l$ 可以在$O(logl)$内求出

总复杂度$O(Klogl)$

void solve() {
int K;
ll M;
cin >> K >> M;

ll P = 10007LL * M;

function<pair<ll,ll>(ll)> calc = [&](ll len) -> pair<ll,ll> {
if (len == 1) return {10 % P, 1 % P};

if (len % 2 == 0) {
auto [A, B] = calc(len / 2);
ll A2 = A * A % P;
ll B2 = B * (A + 1) % P;
return {A2, B2};
} else {
auto [A, B] = calc(len – 1);
return {A * 10 % P, (B * 10 + 1) % P};
}
};

ll cur = 0;
for (int i = 0; i < K; i++) {
int c;
ll l;
cin >> c >> l;

auto [A, B] = calc(l);
cur = (cur * A + 1LL * c * B) % P;
}

cout << cur / M << '\\n';
}

F题

简单概括下题意，要构造一条路径，从1点出发，每个点访问一次回到1，曼哈顿距离不超过$10^{10}$

首先先将所有点按$(x,y)$进行排序，取块的大小为$B=250$，块数最多$\lfloor \frac{60000}{250}\rfloor =240$

对于每个块，将块内点按 $y$ 从小到大排序：

$$q_0,q_1,\dots ,q_{k-1}$$

其中

$$y(q_0)\le y(q_1)\le \cdots \le y(q_{k-1})$$
然后扫描块，假设当前在$y=c$，$y$范围为$[L,U]$，$L=y(q_0),U=y(q_{k-1})$

我们要从最近的端点进块，然后直接扫到另一端

如果 $|c-L|\le |c-U|$，就输出

$$q_0,q_1,\dots ,q_{m-1}$$

否则输出

$$q_{m-1},q_{m-2},\dots ,q_0$$
Proof：

设坐标上界 $M=2\times 10^7$

在 $y$ 方向上：

若$c\le L$

则

$$(L-c)+(U-L)=U-c\le M$$

若$c\ge U$

则

$$(c-U)+(U-L)=c-L\le M$$

若$L\le c\le U$

则

$$\min (|c-L|,|c-U|)+(U-L)\le U-L\le M$$

因此 $y$ 的总代价 $\le 240M$

最后回到起点再加 $M$，因此$\le 241M$

即

$$241\cdot 2\times 10^7=4.82\times 10^9$$

在 $x$ 方向上：

设第 $i$ 块 $x$ 范围$[l_i,r_i]$，记${\Delta }_i=r_i-l_i$

因为块来自按 $x$ 排序后的连续区间，所以

$$\sum {\Delta }_i\le M$$

块内最多 $B-1$ 条边，每条边$|x_i-x_j|\le {\Delta }_i$

因此块内总代价

$$(B-1)\sum {\Delta }_i\le (B-1)M$$

跨块跳跃和最终回边再增加最多 $3M$。

因此 $x$ 的总代价 $\le (B+2)M$

取 $B=250$

$$252M=5.04\times 10^9$$
总距离
$$5.04\times 10^9+4.82\times 10^9=9.86\times 10^9<10^{10}$$
总时间复杂度:$O(NlogN)$