题意
P7116 [NOIP2020] 微信步数 – 洛谷 – 计算机科学教育新生态
给定 $k$ 维场地，场地中的坐标表示为 $(a_1, a_2, \cdots, a_k)$，场地有大小限制 $w$，$1\leq a_i\leq w_i$.
给定 $n$ 个指令构成的指令序列，每个指令用 $(c_i, d_i)$ 表示，代表在第 $c_i$ 维上移动 $d_i\in\{-1, 1\}$。形式化地，若当前位于 $(a_1, a_2, \cdots, a_{c_i}, \cdots, a_k)$，下一步会到 $(a_1, a_2, \cdots, a_{c_i}+d_i, \cdots, a_k)$.
现在，小 $C$ 要从场地中的所有 $P=\prod_{i=1}^k{w_i}$ 个点分别出发，不断重复这个路线，直到其走出场地范围。也就是说，走完 $n$ 步之后，如果小 $C$ 还在场地内，他将回到第 $1$ 步，从头再走一遍。
每执行一次指令代表走一步，求从这 $P$ 个点出发一共走了多少步，对 $10^9+7$ 取模。
若有一天永远走不出场地，输出 $-1$.
| 测试点编号 | $n \le$ | $k \le$ | $w_i \le$ |
|---|---|---|---|
| $1 \sim 3$ | $5$ | $5$ | $3$ |
| $4 \sim 6$ | $100$ | $3$ | $10$ |
| $7 \sim 8$ | ${10}^5$ | $1$ | ${10}^5$ |
| $9 \sim 12$ | ${10}^5$ | $2$ | ${10}^6$ |
| $13 \sim 16$ | $5 \times {10}^5$ | $10$ | ${10}^6$ |
| $17 \sim 20$ | $5 \times {10}^5$ | $3$ | ${10}^9$ |
题解
分析
如果分别计算每个点的话，那复杂度一定会有一个 $\prod_{i=1}^k{w_i}$，所以把每一维分开考虑。
不妨设我们在考虑第 $i$ 维的情况。对于维度 $i$ 的某个位置 $p\in[1, w_i]$，设 $\operatorname{time}_i(p)$ 表示在仅考虑维度 $i$ 时小 C 走出场地需要的最少步数。如果无论如何都无法走出场地那么 $\operatorname{time}_i(p)=+\infty$ 。
注意这里是仅考虑维度 $i$ 时，不考虑先从其他维度走出场地的情况。
求出 $\operatorname{time}$ 这个函数之后，小 C 从 $(a_1,a_2,\dots,a_k)$ 走出场地需要的步数就是 $\min_{i=1}^k\operatorname{time}_i(a_i)$.
因此，题目最终的答案表示为：
\operatorname{Ans} = \sum_{(a_1, a_2\cdots, a_k)\in \operatorname{Map}}\min_{i=1}^k\operatorname{time}_{i}(a_i)
$$
转化
这样求解的复杂度仍是 $\prod_{i=1}^k{w_i}$ 的，不能接受。对上面的式子改变枚举顺序，可以得到：
\operatorname{Ans} = \sum_{(a_1, a_2\cdots, a_k)\in \operatorname{Map}}\min_{i=1}^k\operatorname{time}_{i}(a_i)=\sum_{i\ge 1}\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])
$$
$\sum\limits_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i]$ 代表，在仅考虑第 $j$ 维的情况下，第 $j$ 维中走完 $i$ 步还在地图内的坐标个数。
$\prod\limits_{j=1}^k(\sum\limits_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])$ 代表，走完 $i$ 步仍然在场地内的点的个数。根据乘法原理，把每个维度上可行的坐标乘起来，所得到的就是可行点的个数。
最外层枚举 $i$ 表示：走完 $i$ 步仍然在场地内。
显然，枚举 $i$，把所有可行点数加起来，得到的就是总步数。
容易发现，对这个式子求和的复杂度不再需要 $\prod_{i=1}^k{w_i}$ 了，下面是一种可行的计算方法。
计算方法
假设我们现在已经求出了所有的 $\operatorname{time}_i(j)$.
首先，我们把所有的 $\operatorname{time}_i(j)$ 拿出来，降序排序，同时存储 $\operatorname{time}_i(j)$ 所处的维度。
for(int i = 1; i <= k; i++)
for(int j = 1; j <= w[i]; j++)
T[++cnt] = make_pair(Time[i][j], i);
sort(T + 1, T + cnt + 1);
之后，我们按降序遍历 T[]，对每维开一个桶，记录当前属于该维度的 $\operatorname{time}_i(j)$ 的个数。
当我们枚举到 $T[i]\neq T[i-1]$ 时，此时所有 $\geq T[i]$ 的 $\operatorname{time}_i(j)$ 已经全部加入到了桶中。
把桶上的数累乘，$\prod_{j=1}^k{\operatorname{sum}_j}=\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge T_i])$，就是上面表达式中 $i=T_i$ 时的值，这很显然。
对应到上面 $\operatorname{Ans}$ 的表达式，$i\in[T_{i-1} + 1, T_i]$ 这个范围中的 $\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])$ 都是相同的。
所以 $\operatorname{Ans} += (T_i – T_{i-1})\times \prod_{j=1}^k{\operatorname{sum}_j}$.
pair<int, int> T[10000010]; //first存Time，second存维度
int sum[MAXK]; //sum[i]代表：维度i下，可选的点的个数
int cnt = 0, ans = 0;
for(int i = cnt; i >= 1; i--) {
sum[T[i].second]++;
if(T[i - 1].first != T[i].first) { // >=T[i]的部分已经加入完成
ll tmp = 1;
for(int j = 1; j <= k; j++) tmp *= sum[j];
ans += (T[i].first - T[i - 1].first) * tmp;
}
}
代码没加取模，时间复杂度 $\mathcal{O}(k\cdot \sum w_i)$.
求 $\operatorname{time}_i(j)$
对每个维度分别求。
设 $\operatorname{step}_{i+n}$ 表示在当前枚举的维度上，在一轮内，移动 $i$ 的距离需要的最小步数。由于 $i$ 不一定非负，所以下表要整体加 $n$.
直接设初始在位置 $0$，遍历指令序列即可求出 $\operatorname{step}$，也能求出遍历一遍序列后移动的距离 $\operatorname{cur}$.
如果在一个周期内，$j$ 就可以走出场地，那么此时 $\operatorname{time}_i(j)$ 已经可以求出了。
如果 $j$ 需要多个周期才能出去，我们考虑先求出这个周期数。
不妨设 $j$ 在多个周期后从正方向（$>w_i$）离开场地。
设 $j$ 经过若干个整周期后，位置为 $x$，则其可以在一个新的周期中走出场地，当且仅当 $w_i-x+1\leq \operatorname{Maxdis}$.
$\operatorname{Maxdis}$ 代表，在周期内，最多可以向正方向移动多少距离，这不一定等于周期结束时的移动距离。
因此，周期数可以表示为：
\operatorname{T}=
\left\lceil
\frac{w_i-j+1}{\operatorname{cur}}
\right\rceil
$$
求出了周期数，就可以直接求值了：
\operatorname{time}_i(j)=\operatorname{T}\times n+\operatorname{step}[(w_i-j+1)-\operatorname{T}\times \operatorname{cur}+n]
$$
$+n$ 的原因前面提到过了。
对于从负方向 $<0$ 离开场地的情况也类似，只需要求出 $\operatorname{Mindis}$ 即可。
$\operatorname{Maxdis}$ 和 $\operatorname{Mindis}$ 可以在求 $\operatorname{step}$ 的时候顺便处理出来。
int step[MAXN << 1];
int Time[MAXK][MAXWI];
for(int i = 1; i <= k; i++) {//第i维
memset(step, 0x3f, sizeof(step)); step[n] = 0;
int cur = 0, maxdis = 0, mindis = 0;
for(int j = 1; j <= n; j++) if(c[j] == i) {
cur += d[j];
if(cur > maxdis) maxdis = cur;
if(cur < mindis) mindis = cur;
step[cur + n] = min(step[cur + n], j);
}
//cur: 走n步，一个周期能移动cur
for(int j = 1; j <= w[i]; j++) {
//一个周期就能走到的情况
if(w[i] - j + 1 + n >= 0 && w[i] - j + 1 <= n)
Time[i][j] = min(Time[i][j], step[w[i] - j + 1 + n]);
if(n - j >= 0) Time[i][j] = min(Time[i][j], step[-j + n]);
int rest = 0, tim = 0, T;
//多个周期才能走到的情况
if(cur > 0) { //向正方向
rest = w[i] - j + 1;
T = max(0ll, (rest - maxdis - 1) / cur + 1); //上取整
tim = T * n + step[rest - T * cur + n];
Time[i][j] = min(Time[i][j], tim);
}
if(cur < 0) { //向负方向
rest = j;
T = max(0ll, (rest + mindis - 1) / (-cur) + 1); //上取整
tim = T * n + step[-rest + T * (-cur) + n];
Time[i][j] = min(Time[i][j], tim);
}
}
}
这样实现的时间复杂度同样为：$\mathcal{O}(k\cdot \sum w_i)$.