自动搬运

查看原文

来自洛谷，原作者为

	wxzzzz ·

搬运于2025-08-24 22:45:25，当前版本为作者最后更新于2024-09-15 14:16:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

由于前一天打完 CF 还打了一会儿 florr，导致赛时写了 1h 假做法，然后又似睡非睡地过了 30min，突然发现暴力很好优化，写了 30min 就过了。

思路

设 $f_{i,j}$ 表示最后选的区间为 $[i,j]$ 时的方案数。（这是一个滚动数组，随着枚举当前区间而更新，以节省空间）

$$f_{i,j}=\sum_{[x,y]\cap[i,j]\ne\varnothing}f_{x,y} $$

取出所有与 $[i,j]$ 有交集的区间太麻烦且不好优化，故容斥：

$$f_{i,j}=\sum_{1\le x\le y\le n}f_{x,y}-\sum_{1\le x\le y<i}f_{x,y}-\sum_{j<x\le y\le n}f_{x,y} $$

因此需要维护 $sl_i=\displaystyle\sum_{1\le x\le y\le i}f_{x,y},sr_i=\displaystyle\sum_{i\le x\le y\le n}f_{x,y}$，有：

$$f_{i,j}=sl_m-sl_{i-1}-sr_{j+1}$$

发现转移只关心 $f$ 的某段前缀或后缀的和，故优化状态：$f_{i,j}$ 为原 $f_{j,i}$ 的前缀和，$g_{i,j}$ 为原 $f_{i,j}$ 的后缀和。注意，这里 $f$ 优化后的状态用 $i$ 表示区间右端点，这是为了方便后续优化，因为要钦定右端点取值范围在某一点左边。

现在有：

$$sl_i=sl_{i-1}+\sum_{j\le i} f_{i,j}$$ $$sr_i=sr_{i+1}+\sum_{j\ge i} g_{i,j}$$ $$f_{i,j}=f_{i,j-1}+sl_m-sl_{j-1}-sr_{i+1}$$ $$g_{i,j}=f_{i,j+1}+sl_m-sl_{i-1}-sr_{j+1}$$

注意到转移都是将所有钦定区间某端点后取所有区间，因此进一步优化状态：

$f_i$ 表示当前区间右端点为 $i$ 的所有合法方案之和，$g_i$ 表示当前区间左端点为 $i$ 的所有合法方案之和。

有：

$$\begin{aligned} f_i&=\sum_{j=1}^i(sl_m-sl_{j-1}-sr_{i+1})\\ &=i\times (sl_m-sr_{i+1})-\sum_{j=1}^i sl_{j-1}\\ g_i&=\sum_{j=i}^m(sl_m-sl_{i-1}-sr_{j+1})\\ &=(m-i+1)\times(sl_m-sl_{i-1})-\sum_{j=i}^m sr_{j+1} \end{aligned}$$

上面两式的末项均可前缀和维护。

最后 $sl,sr$ 的转移是容易的：

$$sl_i=sl_{i-1}+f_i$$ $$sr_i=sr_{i+1}+g_i$$

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long ans, MOD, f[10000005], g[10000005], sl[10000005], sr[10000005], ssl[10000005], ssr[10000005];
long long mod(long long x) {
    return x % MOD;
}
int main() {
    cin >> n >> m >> MOD;
    for (int i = 1; i <= m; i++)
        f[i] = mod(i);
    for (int i = m; i >= 1; i--)
        g[i] = mod(m - i + 1);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            sl[j] = mod(sl[j - 1] + f[j]);
        for (int j = m; j >= 1; j--)
            sr[j] = mod(sr[j + 1] + g[j]);
        for (int j = 1; j <= m; j++)
            ssl[j] = mod(ssl[j - 1] + sl[j]);
        for (int j = m; j >= 1; j--)
            ssr[j] = mod(ssr[j + 1] + sr[j]);
        for (int j = 1; j <= m; j++)
            f[j] = mod(j * (sl[m] - sr[j + 1]) - ssl[j - 1]);
        for (int j = 1; j <= m; j++)
            g[j] = mod((m - j + 1) * (sl[m] - sl[j - 1]) - ssr[j + 1]);
    }
    for (int i = 1; i <= m; i++)
        ans = mod(ans + g[i]);
    ans = mod(ans + MOD);
    cout << ans;
    return 0;
}