自动搬运

查看原文

来自洛谷，原作者为

	沉石鱼惊旋 已完成今日我对着铁质的凳子踢了五下然后把那堆钢栏杆在地上滚了一下然后把椅子夹在了篮筐上大学习

搬运于2025-08-24 23:12:17，当前版本为作者最后更新于2025-04-07 16:16:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

做法

考虑先把 $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,0}=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=c_{i-1},y=c_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,0)$ 考虑如果在 $c_i-1$ 的位置取到了 $p_{c_i-1}=y$，那么 $c_i$ 的位置不一定会取到 $y$，要减掉一部分方案。

$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

#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;
}