题解 AT5697 【[AGC041F] Histogram Rooks】

· · 题解

题意 ：有一个 n 行的棋盘，第 i 行的长度为 h_i ，左侧对齐。

该棋盘上放置“車”棋子，若一个格子和某个“車”同行或同列，且之间都是棋盘，则称该格子被覆盖。

求将该棋盘完全覆盖的放置方案数。

答案对 998244353 取模。

------------ AT 题目总是让人一看就很想知道答案，但是想半分钟就会发现根本不可做。 市面上的题解都比较意识流，看了半天才看懂，这里整理一个详细一点的…… 考虑容斥，选（钦定） $k$ 个格子没有被覆盖，容斥系数为 $(-1)^k$。 此时对于某个还能放置車的格子，方案数就是 $2$。 这个做法虽然很直观易懂，但是还没有利用题目的任何性质。考虑对“不可放置”这一条件进行化简。 不难发现，由于行总是连续的，若某一行选了一个格子，则这一整行都不能放置車。 枚举不能放置車的行集合 $S$（不是钦定）。这样，就只需要再考虑列的约束，行列能独立了。 所以，对于每个独立的部分，即**列**上的一个极长连续段，计算出贡献，然后乘起来即可。 若列连续段长度为 $len$ 且有 $p$ 个格子在 $S$ 中，贡献有如下两种 ： - ① 没有格子被选，则所有不在 $S$ 中的格子都能放置，方案数为 $2^{len-p}$。 - ② 枚举选格子的个数，贡献为 $\sum\limits_{i=1}^p\binom{p}{i}(-1)^i=-[p>0]$。 但这个做法是错误的，因为不能保证 $S$ 中的每行都至少有一个点被选。 那就……再容斥！ 钦定不能选格子的行集合 $T\subseteq S$，容斥系数是 $(-1)^{|T|}$。 若列连续段中有 $q$ 个格子在 $S$ 中，则还能选的格子个数只剩下 $p-q$ ，二类贡献变为 $-[p-q>0]=-[p>q]$。 现在正确性有保证了，然而枚举 $S,T$ 的复杂度太高，所以接下来寻找反射。 不难发现，一个列连续段最终的贡献只与 $p,[p=q]$ 有关。（$q$ 要么 $=p$ 要么 $<p$） 前面的做法指出了映射 “ $(S,T)\rightarrow $ 各个连续段 $p,[p=q]$ ” ，现在我们反过来，对某个贡献已经确定的局面，寻找所有可能的 $(S,T)$ 的 $(-1)^{|T|}$ 的和。 坏消息是，在统计 $(S,T)$ 时，列连续段之间不再是独立的。也就是说，该连续段计数的不同的 $(S,T)$ 对其他连续段有不同的影响，所以不能简单地乘法原理了事。 具体地，影响的方式如下 ： 观察棋盘的形状，将其剖分成笛卡尔树的形式，如图 ：（图是蒯 @Itst 神的） ![stO Itst Orz](https://cdn.luogu.com.cn/upload/image_hosting/2xxvstz5.png) 好在，我们只关心 $p,[p=q]$ 。 在某个确定的 $(S,T)$ 局面中，有如下显然事实 ： 红色部分的某一列在 $S$ 中的行的数量 $=$ 绿色部分在 $S$ 中的行的数量 $+$ 蓝色部分在 $S$ 中的行的数量 $+$ 第四行是否在 $S$ 内。 红色部分的某一列的 $[p=q]=($ 绿色部分的 $[p=q]\ ){\ \rm and\ }($ 蓝色部分的 $[p=q]\ ){\ \rm and\ }($ 第四行的 $[p=q]\ )

这启发我们在笛卡尔树上做树形 \rm DP。

设 f\big[u,p,[0=q]\big] 为 ： 对笛卡尔树的节点 u ，其 p,q 为给定情况，所有 (S,T) 的 (-1)^{|T|} 且乘上儿子所有贡献的和。

转移时，p 那一维是背包，而 [p=q] 那一维是 \rm and。具体可见代码。

对于右侧没东西的行，可以看作特殊的儿子。

复杂度为树上背包的复杂度，即 O(n^2)。

求出 f\big[u,p,[0=q]\big] 后，计算出自己一列的贡献，再 pow 一下列数，就能得到自己的贡献。

若每次都 pow ，复杂度可以达到 O(n^2\log n)。但不难发现本质不同的贡献只有 n 种， O(n^2) 预处理幂即可。

#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 405
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
ll c[MaxN][MaxN][2];
void Init(int n)
{
  ll buf=1;
  for (int i=0;i<=n;i++){
    c[i][0][0]=c[i][0][1]=1;
    for (int j=1;j<=n;j++){
      c[i][j][1]=c[i][j-1][1]*buf%mod;
      c[i][j][0]=c[i][j-1][0]*(buf-1)%mod;
    }buf=buf*2%mod;
  }
}
vector<int> g[MaxN];
int siz[MaxN],len[MaxN];
ll f[MaxN][MaxN][2];
void dfs(int u)
{
  if (!u)return ;
  f[u][0][1]=1;
  for (int i=0,v;i<g[u].size();i++){
    dfs(v=g[u][i]);
    siz[u]+=siz[v];
    for (int k=siz[u];k>=0;k--){
      ll sav0=0,sav1=0;
      for (int j=0;j<=min(siz[v],k);j++){
        ll buf=(f[v][j][0]+f[v][j][1])*(f[u][k-j][0]+f[u][k-j][1])%mod,
           buf2=f[v][j][1]*f[u][k-j][1]%mod;
        sav0+=buf-buf2;sav1+=buf2;
      }f[u][k][0]=sav0%mod;
      f[u][k][1]=sav1%mod;
    }
  }for (int p=0;p<=siz[u];p++){
    f[u][p][0]=f[u][p][0]*c[siz[u]-p][len[u]][0]%mod;
    f[u][p][1]=f[u][p][1]*c[siz[u]-p][len[u]][1]%mod;
  }
}
int n,h[MaxN],tn;
int build(int l,int r,int pre)
{
  int mx=*min_element(h+l,h+r+1),
      u=++tn,p=l;
  len[u]=mx-pre;
  for (int i=l;i<=r;i++)
    if (h[i]==mx){
      g[u].pb(0);
      if (p<i)g[u].pb(build(p,i-1,mx));
      p=i+1;
    }
  if (p<=r)g[u].pb(build(p,r,mx));
  return u;
}
int main()
{
  scanf("%d",&n);Init(n);
  for (int i=1;i<=n;i++)
    scanf("%d",&h[i]);
  siz[0]=1;f[0][1][1]=mod-1;f[0][0][1]=f[0][1][0]=1;
  //0节点代表空行 
  int rt=build(1,n,0);
  dfs(rt);
  ll ans=0;
  for (int p=0;p<=n;p++)
    ans+=f[rt][p][0]+f[rt][p][1];
  printf("%lld",(ans%mod+mod)%mod);
  return 0;
}