P9108 [PA2020] Malowanie płotu
题意
有一个 \(n \times m\) 的方格，你需要对每一列涂一个非空连续段，要求相邻列的涂色连续段有交。问涂色方案数。
\(n \times m \le 10^7\)。
思路
我们需要一个 \(O(nm)\) 的算法，但是不好直接设一个 \(O(nm)\) 的状态。
很容易想到设 \(f_{i,l,r}\) 表示考虑到第 \(i\) 列，第 \(i\) 列涂 \([l,r]\) 的方案数。
\[f_{i,l,r} = \sum_{[l',r'] \cap [l,r] \neq \emptyset} f_{i-1,l',r'} \]然后你发现这个交非空直接做是一个三维偏序，可以差分成二维偏序，但是仍然很麻烦。
考虑经典的，变成求全集减去不交的，即：
\[f_{i,l,r} = \sum_{l' \le r'} f_{i-1,l',r'} - \sum_{l' \le r' < l} f_{i-1,l',r'} - \sum_{r < l' \le r'} f_{i-1,l',r'} \]然后我们就可以设
\[s0_{i,j} = \sum_{l \le r \le j} f_{i,l,r},s1_{i,j} = \sum_{j \le l \le r} f_{i,l,r}\\ f_{i,l,r} = s0_{i-1,m} - s0_{i-1,l-1} - s1_{i-1,r+1} \]这样就可以状态 \(O(nm^2)\)，转移 \(O(1)\) 做到总共 \(O(nm^2)\) 的复杂度了。
我们可爱的 \(s\) 数组状态只有 \(O(nm)\)。考虑直接转移 \(s\)。
\[\begin{aligned} s0_{i,j} & = s0_{i,j-1} + \sum_{l\le j} f_{i,l,j}\\ & = s0_{i,j-1} + \sum_{l \le j} s0_{i-1,m} - s0_{i-1,l-1} - s1_{i-1,j+1}\\ & = s0_{i,j-1} + j(s0_{i-1,m} - s1_{i-1,j+1}) - \sum_{l \le j} s0_{i-1,l-1} \end{aligned} \]设
\[t0_{i,j} = \sum_{k \le j} s0_{i,k} \]则
\[s0_{i,j} = s0_{i,j-1} + j(s0_{i-1,m} - s1_{i-1,j+1}) - t0_{i-1,j-1} \]同理，有：
\[t1_{i,j} = \sum_{k \ge j} s1_{i,j}\\ s1_{i,j} = s1_{i,j+1} + (m-j+1)(s0_{i-1,m} - s0_{i-1,j-1}) - t1_{i-1,r+1} \]初始 \(f_{1,l,r} = 1\)，即 \(s0_{1,i} = \frac{i(i-1)}{2} + i,s1_{1,i} = \frac{(m-i+1)(m-i)}{2} + m-i+1\)，答案是 \(\sum f_{n,l,r}\)，即 \(f0_{n,m}\)。
时间复杂度 \(O(nm)\)。
code
要注意一点边界细节。
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace hesitate {
constexpr int N=1e7+7;
int mod;
int add(int a,int b) { return a+b>=mod ? a+b-mod : a+b; }
void _add(int &a,int b) { a=add(a,b); }
int mul(int a,int b) { return 1ll*a*b%mod; }
void _mul(int &a,int b) { a=mul(a,b); }
int n,m;
int s[2][N],t[2][N];
void main() {
sf("%d%d%d",&n,&m,&mod);
rep(j,0,m-1) s[0][j]=add(1ll*j*(j+1)/2%mod,j+1), s[1][j]=add(1ll*(m-j)*(m-j-1)/2%mod,m-j);
t[0][0]=s[0][0], t[1][m-1]=s[1][m-1];
rep(j,1,m-1) t[0][j]=add(t[0][j-1],s[0][j]);
per(j,m-2,0) t[1][j]=add(t[1][j+1],s[1][j]);
rep(i,1,n-1) {
s[0][i*m]=add(s[0][i*m-1],mod-s[1][(i-1)*m+1]);
t[0][i*m]=s[0][i*m];
rep(j,1,m-1) {
int k=i*m+j;
s[0][k]=add(s[0][k-1],add(mul(j+1,add(s[0][i*m-1],mod-s[1][(i-1)*m+j+1])),mod-t[0][(i-1)*m+j-1]));
t[0][k]=add(t[0][k-1],s[0][k]);
}
s[1][i*m+m-1]=add(s[0][i*m-1],m==1 ? 0 : mod-s[0][i*m-2]);
t[1][i*m+m-1]=s[1][i*m+m-1];
per(j,m-2,0) {
int k=i*m+j;
s[1][k]=add(s[1][k+1],add(mul(m-j,add(s[0][i*m-1],j==0 ? 0 : mod-s[0][(i-1)*m+j-1])),mod-t[1][(i-1)*m+j+1]));
t[1][k]=add(t[1][k+1],s[1][k]);
}
}
pf("%d\n",s[0][n*m-1]);
}
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
hesitate :: main();
}