[AGC041F] Histogram Rooks（神仙题 网格 容斥计数）

[AGC041F] Histogram Rooks

给定一个 N" role="presentation">N$N$ 行 N" role="presentation">N$N$ 列的棋盘，第 i" role="presentation">i$i$ 行只有 [1,hi]" role="presentation">[1,hi]$[1,h_i]$ 是有格子的，其他都是虚空。

一个棋子放在一个格子上，我们称一个格子被一个棋子覆盖，仅当这个格子与这个棋子在同一行或同一列，且他们中间没有虚空。特别的，如果这个格子上有棋子，这个格子也被这个棋子覆盖。

求将棋盘上每个格子都覆盖的方案数，对 998244353 取模。

1≤hi≤N≤400" role="presentation">1≤hi≤N≤400$1\le h_i\le N\le 400$。

首先有一个最基础的暴力，直接容斥。钦定集合 S" role="presentation">S$S$ 内的一些格子不被覆盖，其他随意。那么方案数就是 2" role="presentation">2$2$ 的所有不能覆盖这些格子的数量的幂次，乘上容斥系数 (−1)|S|" role="presentation">(−1)|S|$(-1{)}^{|S|}$ 累加即可。

观察求方案的过程发现，如果在一行钦定了一个格子不选，则整一行都不能放棋子，而且行是连续的，列是不连续的，不妨将行作为一个整体进行。

枚举选择了格子的集合 S" role="presentation">S$S$，这里面不能放置棋子。那么取出所有连续的列，计算方案数，再乘起来。

设列的长度为 len" role="presentation">len$len$，其中有 p" role="presentation">p$p$ 行在 S" role="presentation">S$S$ 集合中：

• 如果在这一列没有选择格子，则都可以放置棋子，方案数 2len−p" role="presentation">2len−p$2^{len-p}$；
• 如果在选择了格子，那么整一列不能放置，选择格子的方案数为 ∑i=1p(pi)×(−1)i=−[p>0]" role="presentation">∑pi=1(pi)×(−1)i=−[p>0]$\sum _{i=1}^p(\genfrac{}{}{0ex}{}{p}{i})\times (-1{)}^i=-[p>0]$。

上面式子中由于 ∑i=1p(pi)×(−1)i" role="presentation">∑pi=1(pi)×(−1)i$\sum _{i=1}^p(\genfrac{}{}{0ex}{}{p}{i})\times (-1{)}^i$ 是原来暴力容斥中式子的一部分，也可以理解成容斥原理中负的包含一件物品的方案，减去包含两件物品，加上包含三件物品……等于包含所有物品的方案数等于 −1" role="presentation">−1$-1$。

但是，仅仅这样判断不能保证 S" role="presentation">S$S$ 集合中所有的行都能被覆盖到，再进行一波容斥！

设 T(T∈S)" role="presentation">T(T∈S)$T(T\in S)$ 集合表示在 S" role="presentation">S$S$ 集合中钦定的不能格子的行，其他随意，容斥系数 (−1)|T|" role="presentation">(−1)|T|$(-1{)}^{|T|}$。

设列有 p" role="presentation">p$p$ 个在 S" role="presentation">S$S$ 集合中，有 q" role="presentation">q$q$ 个在 T" role="presentation">T$T$ 集合中：

• 这一列没有选择格子，方案数 2len−p" role="presentation">2len−p$2^{len-p}$；
• 如果选择了格子，选择的方案数为 ∑i=1p−q×(−1)i=−[p>q]" role="presentation">∑p−qi=1×(−1)i=−[p>q]$\sum _{i=1}^{p-q}\times (-1{)}^i=-[p>q]$。

这样只用枚举出 S" role="presentation">S$S$ 和 T" role="presentation">T$T$ 集合就完成了，但枚举量仍然过于庞大。。

在同一列中，它的方案数为 2len−p" role="presentation">2len−p$2^{len-p}$ 还是 2len−p−1" role="presentation">2len−p−1$2^{len-p}-1$ 只取决于 p" role="presentation">p$p$ 是否等于 q" role="presentation">q$q$，因为 p≥q" role="presentation">p≥q$p\ge q$。

计算需要减去的贡献，就相当于计算 [p=q]" role="presentation">[p=q]$[p=q]$ 对应的所有可能的 (S,T)" role="presentation">(S,T)$(S,T)$ 的 (−1)|T|" role="presentation">(−1)|T|$(-1{)}^{|T|}$ 的和，但是列之间会有依赖关系，不再独立。

这样依赖的关系很像 SP3734 PERIODNI - Periodni，图都是一样的，将网格剖分成笛卡尔树的形式。

设 dpi,j,[p=q]" role="presentation">dpi,j,[p=q]$d{p}_{i,j,[p=q]}$ 表示在连续块 i" role="presentation">i$i$ 中 S,T" role="presentation">S,T$S,T$ 都选择了 j" role="presentation">j$j$ 行，S" role="presentation">S$S$ 是否仍然等于 T" role="presentation">T$T$ 的方案数。

• 这个连续块中依然保持 p=q" role="presentation">p=q$p=q$，从儿子中 [p=q]" role="presentation">[p=q]$[p=q]$ 转移过来。
• 否则，总方案减去上面 [p=q]" role="presentation">[p=q]$[p=q]$ 的方案数量就是剩余方案数。

在每个连续段中方案数就等于 2len−p−[p=q]" role="presentation">2len−p−[p=q]$2^{len-p}-[p=q]$ 的长度次幂。

将连续段空行的儿子当做特殊的儿子，上面取就是 −1" role="presentation">−1$-1$，不取就是 1" role="presentation">1$1$。

用树形 DP 完成啦！

#define Maxn 405
#define mod 998244353
int n,tot,All,ans;
int len[Maxn],h[Maxn],siz[Maxn];
int pow2[Maxn][Maxn][2],dp[Maxn][Maxn][2],tmp[Maxn][2];
vector<int> g[Maxn];
inline void init()
{
	for(int i=0,cur=1;i<=n;i++)
	{
		pow2[i][0][0]=pow2[i][0][1]=1;
		for(int j=1;j<=n;j++)
			pow2[i][j][1]=1ll*cur*pow2[i][j-1][1]%mod,
			pow2[i][j][0]=1ll*(cur-1+mod)%mod*pow2[i][j-1][0]%mod;
		cur=cur*2ll%mod;
	}
}
int build(int l,int r,int cur)
{
	int minn=inf,num=++All,Last=l-1;
	for(int i=l;i<=r;i++) minn=min(minn,h[i]);
	for(int i=l;i<=r;i++)
		if(h[i]==minn)
		{
			if(Last+1<=i-1) g[num].pb(build(Last+1,i-1,minn));
			g[num].pb(0),Last=i;
		}
	if(Lastpb(build(Last+1,r,minn));
	len[num]=minn-cur;
	return num;
}
void solve(int u)
{
	if(!u) return;
	dp[u][0][1]=1;
	for(int v:g[u])
	{
		solve(v);
		for(int i=0;i<=siz[u]+siz[v];i++) tmp[i][0]=tmp[i][1]=0;
		for(int su=siz[u];su>=0;su--)
			for(int sv=siz[v];sv>=0;sv--)
			{
				ll tall=1ll*(dp[u][su][0]+dp[u][su][1])*(dp[v][sv][0]+dp[v][sv][1])%mod;
				ll tsame=1ll*dp[u][su][1]*dp[v][sv][1]%mod;
				tmp[su+sv][0]=(1ll*tmp[su+sv][0]+tall-tsame+mod)%mod;
				tmp[su+sv][1]=(tmp[su+sv][1]+tsame)%mod;
			}
		for(int i=0;i<=siz[u]+siz[v];i++) dp[u][i][0]=tmp[i][0],dp[u][i][1]=tmp[i][1];
		siz[u]+=siz[v];
	}
	for(int i=0;i<=siz[u];i++)
		dp[u][i][0]=1ll*dp[u][i][0]*pow2[siz[u]-i][len[u]][0]%mod,
		dp[u][i][1]=1ll*dp[u][i][1]*pow2[siz[u]-i][len[u]][1]%mod;
}
int main()
{
	n=rd(),init();
	for(int i=1;i<=n;i++) h[i]=rd();
	siz[0]=1,dp[0][1][1]=mod-1,dp[0][0][1]=dp[0][1][0]=1;
	build(1,n,0),solve(1);
	for(int i=0;i<=n;i++) ans=(1ll*ans+dp[1][i][0]+dp[1][i][1])%mod;
	printf("%d\n",ans);
	return 0;
}