题解：P12032 [USACO25OPEN] Lazy Sort P
沉石鱼惊旋
·
·
题解
做法
考虑先把 B=\operatorname{sorted}(A) 的 A 条件表示出来。
先分析 n=2 的情况。此时只有 a_1\leq a_2 或者 a_1=a_2+1 的情况才是合法的。就是不需要操作或者一次操作可以交换。
同理扩展一下，这里我是手玩了几个然后猜猜猜猜出来的。相当于问 A 能否被分成若干个区间，满足区间内极差不超过 1，并且上一个区间的 \max \leq 这个区间的 \min。就是区间内能够被排好，不同区间也不影响。
再分析一下这个东西，就是设 p_i=\max\limits_{j=1}^i a_i，需要满足 p_i\leq a_i+1。
然后有一个显然的 \mathcal O(nV^2) 的 DP，设 f_{i,j} 表示前 i 个数 p_i=j 的方案数，转移枚举第 i 个数填什么，判断是否能成为前缀 \max。
这个 DP 再套一个前缀和优化可以做到 \mathcal O(nV)，我不知道怎么继续优化了，但是可以验证猜的结论。
然后我就因为不会了在机房被嘲笑了一上午（恼）。
接下来我们考虑如果知道了 p 的序列能还原出多少个 a。
考虑 p 的断层数量 c，就是前缀 \max 的数量。设一共有 c 个断层，那么有 n-c 个位置是可以任选 p_i 或 p_i-1 的。这里贡献是 2^{n-c}。
但是这里我们只知道 p 的首尾项，具体的断层数量 c 我们要枚举。
除了 2^{n-c} 的贡献，剩下的就是 \binom{L-1}{c-1}\times\binom{V}{c-2} 即前缀 \max 的出现的方案。L 是长度，V 是可选的值域范围。由于首尾确定，所以只有 c-2 个可以自选。
这里 V 可能很大，但是枚举的下指标 c 是连续的，组合数可以从 \binom{V}{0} 开始直接暴力算，每次算一下 \binom{V}{c-1} 和 \binom{V}{c} 的差的贡献。
这样我们就解决了 q=2 时的问题。
其他情况相当于若干个 q=2 合并起来。
设 f_{i,j\in\{0,1\}} 表示 p_i=a_i+j 时的方案数。转移就是 f_{i,0}=f_{j,0}\times c(0,0)+f_{j,1}\times c(1,0) 和 f_{i,1}=f_{j,0}\times c(0,1)+f_{j,1}\times c(1,1)。
求出这个系数 c 即可。
令长度为 L，首项为 x，末项为 y 的 p，可以生成出的合法的 a 的个数为 F(L,x,y)。
设此时有 len=c_{i}-c_{i-1}+1,x=v_{i-1},y=v_i。
则有：
\begin{aligned}
c(0, 0) &= F(L, x, y) - F(L - 1, x, y)\\
c(0, 1) &= F(L - 1, x, y + 1)\\
c(1, 0) &= F(L, x + 1, y) - F(L - 1, x + 1, y)\\
c(1, 1) &= F(L - 1, x + 1, y + 1)\\
\end{aligned}
$c(0,1)$ 考虑如果在 $c_i$ 的位置一定取不到 $p_{c_i}=y+1$，所以只能在 $[c_{i-1},c_i)$ 的位置出现了 $y+1$，区间长度小 $1$。
$c(1,0)$ 与 $c(1,1)$ 的推导类似上两个。
实现注意一下细节，因为 $n$ 很大多带个 $\log$ 可能就寄了。逆元和 $2^k$ 这种东西都要线性预处理出来。
# 代码
<https://www.luogu.com.cn/record/212386055>
```cpp
#include <bits/stdc++.h>
using namespace std;
template <int P>
class mod_int
{
using Z = mod_int;
private:
static int mo(int x) { return x < 0 ? x + P : x; }
public:
int x;
int val() const { return x; }
mod_int() : x(0) {}
template <class T>
mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
bool operator==(const Z &rhs) const { return x == rhs.x; }
bool operator!=(const Z &rhs) const { return x != rhs.x; }
Z operator-() const { return Z(x ? P - x : 0); }
Z pow(long long k) const
{
Z res = 1, t = *this;
while (k)
{
if (k & 1)
res *= t;
if (k >>= 1)
t *= t;
}
return res;
}
Z &operator++()
{
x < P - 1 ? ++x : x = 0;
return *this;
}
Z &operator--()
{
x ? --x : x = P - 1;
return *this;
}
Z operator++(int)
{
Z ret = x;
x < P - 1 ? ++x : x = 0;
return ret;
}
Z operator--(int)
{
Z ret = x;
x ? --x : x = P - 1;
return ret;
}
Z inv() const { return pow(P - 2); }
Z &operator+=(const Z &rhs)
{
(x += rhs.x) >= P && (x -= P);
return *this;
}
Z &operator-=(const Z &rhs)
{
(x -= rhs.x) < 0 && (x += P);
return *this;
}
Z operator-() { return -x; }
Z &operator*=(const Z &rhs)
{
x = 1ULL * x * rhs.x % P;
return *this;
}
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o) \
friend T operator o(const Z &lhs, const Z &rhs) \
{ \
Z res = lhs; \
return res o## = rhs; \
}
setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
friend istream &
operator>>(istream &is, mod_int &x)
{
long long tmp;
is >> tmp;
x = tmp;
return is;
}
friend ostream &operator<<(ostream &os, const mod_int &x)
{
os << x.val();
return os;
}
};
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
x = 0;
int f = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
f = -f;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
read(x);
read(y...);
}
const int P = 1000000007;
using Z = mod_int<P>;
int n, q;
int l, r;
int x, y;
Z ans = 1;
Z f[2];
Z g[2];
Z inv[5000020];
Z pw[5000020];
struct binom
{
int n, i;
Z r;
void init(int m)
{
n = m;
i = 0;
r = 1;
}
Z C(int j)
{
if (n < 0 || j < 0 || n < j)
return 0;
while (i + 1 <= j)
{
i++;
r *= n - i + 1;
r *= inv[i];
}
return r;
}
};
Z calc(int len, int x, int y)
{
if (x > y)
return 0;
if (len == 1 && x != y)
return 0;
if (x == y)
return pw[len - 1];
Z s = 0;
binom C1, C2;
C1.init(len - 1);
C2.init(y - x - 1);
for (int c = 2; c <= min(y - x + 1, len); c++)
{
s += C1.C(c - 1) *
C2.C(c - 2) *
pw[len - c];
}
return s;
}
int main()
{
read(n, q);
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = inv[P % i] * (P - P / i);
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = pw[i - 1] * 2;
l = -1;
f[0] = 1;
while (q--)
{
read(r, y);
if (~l)
{
memcpy(g, f, sizeof(g));
memset(f, 0, sizeof(f));
Z c00 = calc(r - l + 1, x, y) - calc(r - l, x, y);
Z c01 = calc(r - l, x, y + 1);
Z c10 = calc(r - l + 1, x + 1, y) - calc(r - l, x + 1, y);
Z c11 = calc(r - l, x + 1, y + 1);
f[0] += g[0] * c00;
f[0] += g[1] * c10;
f[1] += g[0] * c01;
f[1] += g[1] * c11;
}
l = r;
x = y;
}
cout << f[0] + f[1] << '\n';
return 0;
}
```