[ARC132C] Almost Sorted
本题的状压并不是很明显，但是因为 \(d\) 很小，所以应该想到。
可以用差值来设计状态。
令 \(f[i][j]\) 表示填完前 \(i\) 个数，目前 \([-d,d]\) 的差值中可用的状态为 \(j\) 的方案数。
考虑枚举上一个位置：
- 第 \(i\) 个位置选的数不能再上一个位置的集合中出现
- 需要保证现在选的数是可以选到的，即要么这个位置随意填数，要么这个位置本来就是要填的数
- 不越界
满足以上条件之后，就可以进行状态转移了。
f[i][(j | (1<<(d+k))) >> 1] = (f[i][(j | (1<<(d+k))) >> 1]+f[i-1][j])%mod
其中的 \(k\) 是枚举的新入的数，需要 \(d\) 的偏移，然后加入 \(j\) 集合。然后因为是下一个位置，所有的 \(p_i-i\) 集合需要减小 \(1\)，\(>>1\) 即可。
答案是 \(f[n][2^d-1]\)，因为前 \(n\) 个数均填完，所以 \([-d,-1]\) 范围内的数均已填过。
复杂度 \(O(n2^{2d+1})\)。
标签：AlmostSorted,位置,个数,枚举,差值,集合 From： https://www.cnblogs.com/wscqwq/p/17575667.html