ABC270Ex add 1

题意：有 $n$ 个计数器，每个计数器有一个上界 $a_i$，每次操作会将一个计数器清 0，然后将其他计数器 +1。问期望多少步每个计数器都达到上界。保证 $0 = a_1 \leq a_2 \leq \dots\leq a_n\leq 10 ^ {18}$，$a_n > 0$，$n\leq 2\times 10 ^ 5$，答案对 998244353 取模。

好神的期望题。

首先 $n$ 个状态显然是不好计数的，我们考虑用一个状态描述。记 $k$ 为 $\max_{i = 1} ^ n(a_i - c_i)$，$c_i$ 表示当前的计数器的数。记录 $f_k$ 表示从状态 $k$ 期望的步数结束。容易发现 $f_0 = 0$。

考虑设一个 $r$ 为最大的满足 $a_r < k\leq a_{r + 1}$ 的阈值，我们考虑分析两种情况：

1. 选中清空的 $i$ 满足 $i\leq r$。这时不管清空的是哪一个，我们都容易得到新的状态是 $k - 1$。
2. 选中清空的 $i$ 满足 $i > r$。这是清空哪一个，$k$ 就会变成哪一个计数器的值。所以就会变成 $a_i$。

那么据此我们可以得到：

$$f_k = \dfrac rn f_{k - 1} + \dfrac 1n \sum_{i = r + 1} ^ n f_{a_i} + 1$$

注意到转移方向不确定，我们考虑变化一下，这样 $f_{k - 1}$ 在一边了。

但是我们又注意到一个问题，就是我们知道的不是最大的那一个，而是最小的那一个（$f_0 = 0$）。

考虑转化定义，设 $g_k$ 表示开始期望多少能走到状态 $k$。容易发现 $f_k + g_k = f_{a_n}$。那么我们现在已经知道了 $g_{a_n} = 0$，我们需要找到 $g_0$。

直接暴力带入上面的式子：

$$\begin{aligned} f_{a_n} - g_{k} =&\dfrac rn(f_{a_n} - g_{k - 1}) + \dfrac 1n \sum_{i = r + 1} ^ n (f_{a_n} - g_{a_i}) + 1\\ g_k =& \dfrac rn g_{k - 1} + \dfrac 1n \sum_{i = r + 1} ^ n g_{a_i} - 1\\ g_{k - 1} =& \dfrac nr g_k - \dfrac 1r \sum_{i = r + 1} ^ n g_{a_i} + \dfrac nr \end{aligned}$$

得到这样的式子过后，我们可以得到一个 $O(a\log a)$ 的做法。但是仍然不够优秀，我们考虑优化。

容易发现在 $k\in (a_r, a_{r + 1}]$ 的转移都是相同的，因为 $r$ 不变。我们考虑从这里入手。我们记 $suf_r = \sum_{i = r} ^ n g_{a_i}$，有：

$$\begin{aligned} g_{k - 1} =& \dfrac nr g_k - \dfrac {suf_{r + 1}}r + \dfrac nr\\ g_{k - 1} - \dfrac {suf_{r + 1}}{n - r} + \dfrac n{n - r} =& \dfrac nr(g_k - \dfrac {suf_{r + 1}}{n - r} + \dfrac n{n - r}) \end{aligned}$$

注意到我们把两边的形式化为相同过后，直接快速幂，这个可以省去中间的状态，直接通过 $g_{a_{r + 1}}$ 得到 $g_{a_r}$。

$$g_{a_r} + \dfrac {n - suf_{r + 1}}{n - r} = \left(\dfrac nr \right) ^ {a_{r + 1} - a_r} (g_{a_{r + 1}} + \dfrac {n - suf_{r + 1}}{n - r})$$

直接计算可以得到 $O(n\log a)$，可以通过。

int main()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) scanf("%lld", a + i);
	for (int i = n - 1, x, tmp; i; -- i) {
		x = qpow((LL) n * qpow(i) % Mod, a[i + 1] - a[i]);
		res[i] = (res[i + 1] + (LL) adj(tmp = n - suf[i + 1]) * qpow(n - i)) % Mod * x % Mod;
		res[i] = (res[i] + (LL) (Mod - tmp) * qpow(n - i)) % Mod;
		adj(suf[i] = suf[i + 1] + res[i] - Mod);
	}
	std::cout << res[1] << '\n';
	return 0;
}