题目链接
题目解法
好牛（难）的题！！！
所有都被覆盖 不难想到容斥
暴力的容斥是钦定集合 \(S\) 中的位置都没被覆盖，然后把不能填棋子的点都去掉，假设剩下的不受限制的点的个数为 \(c\)，则答案为 \(\sum 2^c(-1)^{|S|}\)
这个暴力是很难直接优化的
如果一列被有点被钦定了，那么这一列就不能有棋子了，所以我们转而枚举列的集合 \(State\)（注意不是钦定，即我们实际还是在容斥没有覆盖的位置）
对于每一个行的连续段的结果显然是独立的，考虑计算每一个行的连续段的容斥值，然后乘起来
假设当前连续段长度为 \(len\)，且中间包含 \(c\) 个 \(State\) 中的列
直觉上，容斥值是这样的：
- 连续段中没有棋子被钦定，结果为 \(2^{len}\)
- 连续段中有棋子被钦定，结果为 \(\sum\limits_{x=1}^c (-1)^x\binom{c}{x}=[c>0]\)
但这样其实是错的，因为不能保证 \(State\) 中每一列都有点被钦定
考虑继续容斥
枚举 \(T\subseteq State\)，表示 \(T\) 集合中的列需要点被钦定，但实际没有点被钦定
我们令当前连续段中有 \(c'\) 列在 \(T\) 中，那么容斥值变成了：
- 连续段中没有棋子被钦定，结果为 \(2^{len}\)
- 连续段中有棋子被钦定，结果为 \(\sum\limits_{x=1}^{c-c'} (-1)^x\binom{c-c'}{x}=[c>c']\)
因为 \(T\subseteq S\)，所以 \(c'\le c\)，即我们只有 \(2\) 个状态：\(c'<c\) 和 \(c'=c\)
接下来咋做？考虑用这道题的思路
我们建出笛卡尔树
这里可以看一下 \(verdandi\) 的图，我们把网格切成若干个行连续段，且把相同的行连续段归在一起
我们在笛卡尔树上 \(dp\)，就可以对这东西进行统计
可以发现，上面的容斥系数只和 \(c\) 和 \([c'=c]\) 有关，所以 \(dp\) 中只要记录这两个东西
令 \(f_{i,j,0/1}\) 表示在 \(i\) 的子树中，\(j\) 为上文的 \(c\)，是否有 \(c'=c\) 的方案数
转移类似树形背包合并，\(0/1\) 的合并类似与
最后乘上若干行连续段的贡献即可
边界（即子树根，空列）为 \(f_{i,0,1}=f_{i,1,0}=1,f_{i,1,0}=-1\)
预处理幂可以做到 \(O(n^2)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=410,P=998244353;
int n,h[N],son[N][2];
int build(int l,int r){
if(l>r) return 0;
int mn=l;
F(i,l+1,r) if(h[mn]>h[i]) mn=i;
son[mn][0]=build(l,mn-1),son[mn][1]=build(mn+1,r);
return mn;
}
int f[N][N][2],g[N][2],siz[N],pw[2][N][N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
void dfs(int u,int hig){
siz[u]=1;
f[u][0][1]=f[u][1][0]=1,f[u][1][1]=P-1;
F(i,0,1){
int v=son[u][i];if(!v) continue;
dfs(v,h[v]-h[u]);
F(j,0,siz[u]+siz[v]) F(k,0,1) g[j][k]=0;
F(j,0,siz[u]) F(p,0,1) F(k,0,siz[v]) F(q,0,1) inc(g[j+k][p&q],1ll*f[u][j][p]*f[v][k][q]%P);
siz[u]+=siz[v];
F(j,0,siz[u]) F(k,0,1) f[u][j][k]=g[j][k];
}
F(j,0,siz[u]) F(k,0,1) f[u][j][k]=1ll*f[u][j][k]*pw[!k][siz[u]-j][hig]%P;
}
int main(){
n=read();
F(i,1,n) h[i]=read();
F(i,0,1){
int v=1;
F(j,0,n){
pw[i][j][0]=1;
F(k,1,n) pw[i][j][k]=1ll*pw[i][j][k-1]*(v+P-i)%P;
v=v*2%P;
}
}
int rt=build(1,n);dfs(rt,h[rt]);
int ans=0;
F(i,0,n) F(j,0,1) inc(ans,f[rt][i][j]);
printf("%d\n",ans);
return 0;
}