专栏文章

ULR T2

wwzj33300想成为人类
休闲·娱乐参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min14im9
此快照首次捕获于
2025/12/01 18:51
3 个月前
此快照最后确认于
2025/12/01 18:51
3 个月前
查看原文
题目链接
首先我们刻画操作，由于最后必须回到原点，所以我们可以先考虑把操作分成很多个“从原点走到一个点再走回来”的路径，考虑这样走相当于在左端点 −1-1，右端点 +1+1。但是同时注意到可以任意选这样的区间，只要从原点走到的最远点比这个区间还远，于是我们可以刻画成这样：
考虑判定一个数列 bb 是否能被到达，先判掉 a=ba=b 的情况。首先对 aa 和 bb 都做前缀和得到 AA 和 BB，那么 BB 有如下要求：
  • An=BnA_n=B_n； 
  • ∀1≤i≤n,Bi≤Ai\forall 1\le i\le n,B_i\le A_i；
  • 所有 Ai≠BiA_i\ne B_i 的位置形如一个区间，且这个区间包含 p−1p-1 或 pp，其中 pp 为原点。
  • 注意 bb 是非负的，所以 ∀1<i≤n,Bi−1≤Bi\forall 1<i\le n,B_{i-1}\le B_i。
这时你可以直接对前后缀 dp 这个条件，可以做到 O(n∑a)O(n\sum a)。
我们先强制 Bn=AnB_n=A_n，就可以把这个条件扔掉；钦定 Ai≠BiA_i\ne B_i 的区间为 [l,r][l,r]，考虑容斥 Bi−1≤BiB_{i-1}\le B_i，现在我们钦定了几条边不合法，剩下的边随意。对于每个不合法的连续段 [L,R][L,R]（单点也算一个连续段），由于 AA 是非降的，所以方案数就是在 [Al−1,AL)[A_{l-1},A_L) 中选 R−L+1R-L+1 个数。这里下限为 Al−1A_{l-1} 是因为我们已经强制 B[<l]B[<l] 的数都等于 AA，我们要保持 Bl−1≤BlB_{l-1}\le B_{l}。
考虑枚举区间的左端点 ll，则右侧区间内的每个数取值在 [sl−1,si)[s_{l-1}, s_i) 之间。令 f(r)f(r) 表示容斥原理的某个分段以 rr 结尾的方案数，初值为 f(l−1)=1f(l-1) = 1，此时有转移
f(i)=∑j=li(Aj−Al−1i−j+1)(−1)i−jf(j−1).f(i) = \sum_{j=l}^i \binom{A_j-A_{l-1}}{i-j+1} (-1)^{i-j} f(j-1).
考虑计算答案的过程，除了 a=ba=b 的答案，我们需要计算符合那个加粗的条件的方案数，做差，就是 #[r≥p−1]−#[l>p]\#[r\ge p-1]-\#[l>p]。可以看出我们只关心钦定 ll 或者钦定 rr 的答案，考虑在上面的转移中把与 ll 有关的项去掉。由于我们钦定下限为 sl−1s_{l-1} 只是为了解决 [l−1,l][l-1,l] 的限制，具体来说，我们就是在干这样的事：
我们要保证每个 [i−1,i][i-1,i] 的都满足。那么在 [1,l−1]∪[r+1,n][1,l-1]\cup[r+1,n] 的限制由于 AA 的单调性已经满足，[l,r][l,r] 的限制由我们的容斥解决（容斥顺便解决 Bi<AiB_i<A_i），[r,r+1][r,r+1] 的限制必定满足，所以我们只用考虑在容斥的时候 钦定 Bl≥Bl−1=Al−1B_l\ge B_{l-1}=A_{l-1} 即可。
而这在我们考虑的第一个连续段即可解决，注意我们只用考虑第一个数的范围，所以我们的方案数应该改为 (Aji−j+1)−(Al−1i−j+1)\binom{A_j}{i-j+1}-\binom{A_{l-1}}{i-j+1}，分别是 [0,Aj),[0,Al−1)[0,A_j),[0,A_{l-1})。
设 f[r][0]f[r][0] 表示考虑到 rr，强制当前段为第一段；f[r][1]f[r][1] 不强制，则我们可以写出
f[0][1]=0f[r][0]=∑l=1r[(Alr−l+1)−(Al−1r−l+1)](−1)r−lf[r][1]=f[r][0]+∑l=1r(Alr−l+1)(−1)r−lf[l−1][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]g[l][0] 表示倒着考虑到 ll，强制当前段为（正着的）第一段；g[l][1]g[l][1] 强制不是第一段，则我们可以写出（注意 Bn=AnB_n=A_n，+1+1 是因为可以段可以任意右端点）
g[n][1]=0g[l][0]=∑r=ln−1[(Alr−l+1)−(Al−1r−l+1)](−1)r−l(g[r+1][1]+1)g[l][1]=∑r=ln−1(Alr−l+1)(−1)r−l(g[r+1][1]+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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...