ULR T2
wzj33300
·
2025-11-25 00:36:47
·
休闲·娱乐
题目链接
首先我们刻画操作，由于最后必须回到原点，所以我们可以先考虑把操作分成很多个“从原点走到一个点再走回来”的路径，考虑这样走相当于在左端点 -1 ，右端点 +1 。但是同时注意到可以任意选这样的区间，只要从原点走到的最远点比这个区间还远，于是我们可以刻画成这样：
考虑判定一个数列 b 是否能被到达，先判掉 a=b 的情况。首先对 a 和 b 都做前缀和得到 A 和 B ，那么 B 有如下要求：
这时你可以直接对前后缀 dp 这个条件，可以做到 O(n\sum a) 。
我们先强制 B_n=A_n ，就可以把这个条件扔掉；钦定 A_i\ne B_i 的区间为 [l,r] ，考虑容斥 B_{i-1}\le B_i ，现在我们钦定了几条边不合法，剩下的边随意。对于每个不合法的连续段 [L,R] （单点也算一个连续段），由于 A 是非降的，所以方案数就是在 [A_{l-1},A_L) 中选 R-L+1 个数。这里下限为 A_{l-1} 是因为我们已经强制 B[<l] 的数都等于 A ，我们要保持 B_{l-1}\le B_{l} 。
考虑枚举区间的左端点 l ，则右侧区间内的每个数取值在 [s_{l-1}, s_i) 之间。令 f(r) 表示容斥原理的某个分段以 r 结尾的方案数，初值为 f(l-1) = 1 ，此时有转移
f(i) = \sum_{j=l}^i \binom{A_j-A_{l-1}}{i-j+1} (-1)^{i-j} f(j-1).
考虑计算答案的过程，除了 a=b 的答案，我们需要计算符合那个加粗的条件的方案数，做差，就是 \#[r\ge p-1]-\#[l>p] 。可以看出我们只关心钦定 l 或者钦定 r 的答案，考虑在上面的转移中把与 l 有关的项去掉。由于我们钦定下限为 s_{l-1} 只是为了解决 [l-1,l] 的限制，具体来说，我们就是在干这样的事：
我们要保证每个 [i-1,i] 的都满足。那么在 [1,l-1]\cup[r+1,n] 的限制由于 A 的单调性已经满足，[l,r] 的限制由我们的容斥解决（容斥顺便解决 B_i<A_i ），[r,r+1] 的限制必定满足，所以我们只用考虑在容斥的时候 钦定 B_l\ge B_{l-1}=A_{l-1} 即可。
而这在我们考虑的第一个连续段即可解决，注意我们只用考虑第一个数的范围，所以我们的方案数应该改为 \binom{A_j}{i-j+1}-\binom{A_{l-1}}{i-j+1} ，分别是 [0,A_j),[0,A_{l-1}) 。
设 f[r][0] 表示考虑到 r ，强制当前段为第一段；f[r][1] 不强制，则我们可以写出
\begin{aligned}
f[0][1]&=0\\
f[r][0]&=\sum_{l=1}^r\left[\binom{A_l}{r-l+1}-\binom{A_{l-1}}{r-l+1}\right](-1)^{r-l}\\
f[r][1]&=f[r][0]+\sum_{l=1}^r\binom{A_l}{r-l+1}(-1)^{r-l}f[l-1][1]
\end{aligned}
设 g[l][0] 表示倒着考虑到 l ，强制当前段为（正着的）第一段；g[l][1] 强制不是 第一段，则我们可以写出（注意 B_n=A_n ，+1 是因为可以段可以任意右端点）
\begin{aligned}
g[n][1]&=0\\
g[l][0]&=\sum_{r=l}^{n-1}\left[\binom{A_l}{r-l+1}-\binom{A_{l-1}}{r-l+1}\right](-1)^{r-l}(g[r+1][1]+1)\\
g[l][1]&=\sum_{r=l}^{n-1}\binom{A_l}{r-l+1}(-1)^{r-l}(g[r+1][1]+1)\\
\end{aligned}
https://uoj.ac/submission/807362