P9108 [PA2020] Malowanie płotu 题解
wxzzzz
·
·
题解
前言
由于前一天打完 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}
注意到转移都是将所有钦定区间某端点后取所有区间，因此进一步优化状态：
有：
$$\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$$
### 代码
```cpp
#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;
}
```