提出 #65361454

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=405,H=998244353;
int n,h[N],sz[N],f[N][N][2],c[N][N][2],idx=0,len[N],ans;
vector<int> G[N];

int adc(int a,int b){return a+b>=H?a+b-H:a+b;}
int dec(int a,int b){return a<b?a-b+H:a-b;}
int mul(int a,int b){return 1ll*a*b%H;}
void add(int &a,int b){a=adc(a,b);}
void del(int &a,int b){a=dec(a,b);}

int qpow(int a,int b=H-2){
  int res=1;
  while(b){if(b&1) res=mul(res,a);a=mul(a,a),b>>=1;}
  return res;
}

void init(){
  for(int i=0,bas=1;i<=n;i++,bas=mul(bas,2)){
	c[i][0][0]=c[i][0][1]=1;
	for(int j=1;j<=n;j++) for(int k:{0,1}) c[i][j][k]=mul(c[i][j-1][k],bas-(!k));
  }
}

int build(int l,int r,int pre){
  int mn=n+1,u=++idx,lst=l;
  for(int i=l;i<=r;i++) mn=min(mn,h[i]);
  len[u]=mn-pre;
  for(int i=l;i<=r;i++){
	if(h[i]==mn){
	  G[u].pb(0);
	  if(lst<i) G[u].pb(build(lst,i-1,mn));
	  lst=i+1;
	}
  }
  if(lst<=r) G[u].pb(build(lst,r,mn));
  return u;
}

void dfs(int u){
  if(!u) return ;
  f[u][0][1]=1;
  for(int v:G[u]){
	dfs(v),sz[u]+=sz[v];
	for(int j=sz[u];j>=0;j--){
	  array<int,2> t={0,0};
	  for(int i=0;i<=min(sz[v],j);i++)
	    for(int k1:{0,1}) for(int k2:{0,1})
		  add(t[k1&k2],mul(f[v][i][k1],f[u][j-i][k2]));
	  for(int k:{0,1}) f[u][j][k]=t[k];
	}
  }
  for(int i=0;i<=sz[u];i++) for(int k:{0,1})
	f[u][i][k]=mul(f[u][i][k],c[sz[u]-i][len[u]][k]);
}

int main(){
  /*2025.4.30 H_W_Y AT_agc041_f [AGC041F] Histogram Rooks 容斥 + dp*/
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>h[i];
  init(),build(1,n,0);
  sz[0]=1,f[0][1][1]=H-1,f[0][1][0]=f[0][0][1]=1;
  dfs(1);
  for(int i=0;i<=n;i++) for(int k:{0,1}) add(ans,f[1][i][k]);
  cout<<ans;
  return 0;
}

提出情報

ジャッジ結果