老题解批量补档。
http://222.180.160.110:61235/contest/6248/problem/2
给定 \(q\) 次询问，每次给定 \(f(0)\)，求最小的 \(t\)，使得 \(n | f(t)\)，其中 \(f(t)=d\cdot f(t-1) + \Delta_t\)，\(n,d,l,r\) 为常数，\(\Delta_t\) 为你自选的 \([l,r]\) 间的整数，每次询问独立。
\(q, n\le 10^7\)。
如果这是数论题，\(n\) 就不会和 \(q\) 同阶了，所以这可能是一道偏模拟的题目。
很容易想到建同余图（这里说的是从 \([0-r,0-l]\) 出发；这样每个点第一次被 BFS 到的时候就能确定答案了）。但如果直接把图建出来，大小就是 \(O(n^2)\) 级别的了。每次连的点都是连续的一段，容易想到线段树优化建图。这样就能 \(O(n\log n)\) 解决问题了。但是题目要求线性。
在实现的时候一定会注意到我们会连到一些已经被访问过的点。这样的边是『无效』的——我们不能将访问过的点再次加入队列。能不能规避掉这些点呢？
每次被访问过的点一定是连续的、长度为 \(r - l + 1\) 的一段——有没有联想到什么？类似地，给 \(0\sim n-1\) 每隔 \(r-l+1\) 打一个标记——或者说 分一段，那么每次试图访问 \([l_0, r_0]\) 时：
- \([l_0,r_0]\) 为两个相邻段的前后缀。
- \([l_0,r_0]\) 恰好为一段。
这时我们就发现了，每次访问的是完整的前后缀，利用前后缀和优化建图，由于边数是 \(O(n)\) 的，且边权只有 \(0\) 和 \(1\)，就可以做到 \(O(n)\) 01BFS 解决问题。
注：常数大到必可神机跑不过
#include <bits/stdc++.h>
struct IO {
static const int N = 1 << 22;
char buf[N], pbuf[N], *p1 = buf, *p2 = buf, *pp = pbuf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N, stdin), p1 == p2) ? EOF : *p1++)
template <typename T>
void read(T& x) {
x = 0;
char ch;
int f = 0;
while ((ch = gc()) < '0' || ch > '9') f |= (ch == '-');
while (x = (x << 1) + (x << 3) + (ch ^ 48), (ch = gc()) >= '0' && ch <= '9')
;
if (f)
x = ~x + 1;
}
void putc(char c) {
if (pp - pbuf == N)
fwrite(pbuf, 1, N, stdout), pp = pbuf;
*pp++ = c;
}
void puts(const char* s) {
while (*s) putc(*s), ++s;
putc('\n');
}
template <typename T>
void print(T x) {
static int st[20];
int tp = 0;
if (x < 0)
putc('-'), x = ~x + 1;
do
st[++tp] = x % 10, x /= 10;
while (x);
while (tp) putc(st[tp--] + '0');
}
~IO() { fwrite(pbuf, pp - pbuf, 1, stdout); }
} io;
int main() {
#ifdef ONLINE_JUDGE
std::freopen("calculate.in", "r", stdin);
std::freopen("calculate.out", "w", stdout);
#else
std::freopen("ex_calculator3.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (io.read(T); T--; ) {
int n, l, r, m, to;
long long d, len;
io.read(n), io.read(d), io.read(l), io.read(r), io.read(m);
len = r - l + 1, to = (n - 1) / len + 1;
std::vector<std::vector<int> > t(n), lid(to), rid(to);
for (int i = 0; i < n; ++i)
t[i * d % n].push_back(i);
std::vector<std::vector<int> > g(3 * n);
for (int i = 0, id = n - 1; i < to; ++i) {
int at = ((i != to - 1 || !(n % len)) ? len : (n % len));
lid[i].resize(at), rid[i].resize(at);
for (int j = 0; j < at; ++j) {
lid[i][j] = ++id;
g[id].push_back(i * len + j);
if (j != 0)
g[id].push_back(id - 1);
}
for (int j = at - 1; ~j; --j) {
rid[i][j] = ++id;
g[id].push_back(i * len + j);
if (j != at - 1)
g[id].push_back(id - 1);
}
}
auto add = [&](int p, int l0, int r0) {
int p1 = l0 / len, p2 = r0 / len;
if (p1 == p2)
g[p].push_back(lid[p1].back());
else {
g[p].push_back(rid[p1][l0 % len]);
if ((p1 + 1) % to != p2) {
// fprintf(stderr, "p1 = %d, p2 = %d, to = %d, get %d(%d)\n", p1, p2, to, (p1 + 1) % to, (int)lid[(p1 + 1) % to].size());
g[p].push_back(lid[(p1 + 1) % to].back());
}
g[p].push_back(lid[p2][r0 % len]);
}
return;
};
for (int i = 0; i < n; ++i)
for (auto j : t[i]) {
// printf("%d -> %d[%d, %d]\n", i, j, (j + n - r) % n, (j + n - l) % n);
add(i, (j + n - r) % n, (j + n - l) % n);
}
std::list<std::pair<int, int> > q;
std::vector<int> f(n + 1, -1), tag(3 * n + 1);
for (int i = l, p = (n - r) % n; i <= r; ++i, (++p) %= n)
f[p] = 0, q.emplace_back(p, 0), tag[p] = 1;
for (; !q.empty(); ) {
auto [u, d] = q.front();
q.pop_front();
if (u < n)
f[u] = d;
// printf("u = %d, d = %d\n", u, d);
for (auto i : g[u]) {
// printf(" i = %d\n", i);
if (!tag[i]) {
if (i >= n)
q.emplace_front(i, d), tag[i] = 1;
else
q.emplace_back(i, d + 1), tag[i] = 1;
}
}
}
for (int x; m--; )
io.read(x), io.print(f[x]), io.putc('\n');
}
return 0;
}或者，发现每次任意标记前后缀，则一段内未访问的一定是中间的一整截。根据这一点可维护每一段内可访问元素，就能 \(O(n)\) BFS；
如果把图建出来了，还可以解决扩展问题：
假如 \(\Delta_i\) 在 \([l,r]\) 间的整数中等概率取值，则最优解出现的概率？
为什么 BFS 不能解决该问题呢？因为同层同代价的点对共同能访问到的点的贡献不会被 BFS 记入（注意到一个点只会被一个点访问到），所以只有建图出来才能解决问题。
这也侧面反映该图在忽略环后所对应的就是最优解，这其实是有点 BFS 扩展出来的意味在的。