command_block 的博客

command_block 的博客

[DP记录]ARC118E Avoid Permutations

posted on 2021-10-30 16:53:33 | under 记录 |

题意

  • 对于排列 $P_{1\sim n}$ ,定义 $f(P)$ 为:

    有一个 $(n+2)\times (n+2)$ 的矩阵,行列编号分别为 $0\sim n+1$ 。$(i,P_i)$ 为障碍,其余位置无障碍。

    从 $0,0$ 出发,只能向下向右,不能经过障碍,到达 $(n+1,n+1)$ 的方案数。

现在给出一个部分未填的排列 $Q_{1\sim n}$ ,求 $Q$ 的每种填写结果的 $f$ 函数值的和。

答案对 $998244353$ 取模。

$n\leq 200$ ,时限$\texttt{2s}$


考虑 $Q$ 确定时怎么做。

使用容斥原理,枚举一个含 $k$ 个障碍点的集合 $S=\{(x_i,y_i)\}$,强制路径经过这些点,容斥系数为 $(-1)^k$。

为了方便,记 $S_0=(0,0),S_{k+1}=(n+1,n+1)$

方案数为:

$$\prod\limits_{i=1}^{n-1}[x_{i-1}\leq x_i][y_{i-1}<y_i]\dbinom{x_i-x_{i-1}+y_i-y_{i-1}}{x_i-x_{i-1}}$$

用 DP 求解,记 $dp_{i,j}$ 表示前 $i$ 个位置选了 $j$ 个障碍点,且第 $i$ 个位置必选的方案数,枚举下一个障碍点即可转移。

注意到 $j$ 只用于最终计算 $(-1)^j$ 的容斥系数,可以经典地把容斥系数塞进 DP 转移中(每一步乘一次 $-1$),将 $j$ 省去。

$Q$ 不确定时,记已填位置有 $c$ 个,未填的 $x$ 坐标集合为 $X$ ,$y$ 坐标集合为 $Y$ 。

若我们选定的集障碍点集合含有 $m$ 个未填位置,则填写其余未填位置的方案数是 $(n-a-m)!$。

仍然考虑从左到右 DP ,记 $dp_{i,j,k}$ 表示前 $i$ 个位置,第 $i$ 个位置必选且选中的 $y$ 坐标是 $j$ ,共选了 $k$ 个未确定位置的贡献和。

转移时,需要枚举前继状态的 $i,j$ ,复杂度达到了 $O(n^5)$ 。

为了优化,我们不要用组合数“离散地”计算路径方案数,而是回归基于“路径”本身的 DP 方式。

记 $dp_{i,j,k,e_1,e_2}$ 表示路径走到 $(i,j)$ ,共经过 $k$ 个钦定的未填点,当前 行/列 目前 有/无 被钦定的原未填点,的方案数。

转移时,若 $i\in X,j\in Y$ 且 $e_1=e_2=0$ ,则可以在此处钦定一个原未填点。

具体转移见代码。复杂度 $O(n^3)$ 。

答案为 $\sum_k (-1)^k(n-c-k)!dp_{n+1,n+1,k,0,0}$

#include<algorithm>
#include<cstdio>
#define MaxN 205
using namespace std;
const int mod=998244353;
void add(int &a,int b){a=(a+b)%mod;}
int n,c,a[MaxN],b[MaxN],fac[MaxN],dp[MaxN][MaxN][MaxN][2][2];
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++)b[i]=-1;
  for (int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    if (a[i]!=-1){c++;b[a[i]]=1;}
  }
  b[0]=b[a[n+1]=n+1]=1;
  dp[0][0][0][0][0]=1;
  for (int i=0;i<=n+1;i++)
    for (int j=0;j<=n+1;j++)if (i+j==0||i+j==n+n+2||a[i]!=j)
      for (int k=0;k<=n-c;k++)
        for (int e1=0;e1<=1;e1++)
          for (int e2=0;e2<=1;e2++){
            int now=dp[i][j][k][e1][e2];
            if (!now)continue;
            if (i<=n){
              add(dp[i+1][j][k][e1][0],now);
              if (!e1&&a[i+1]==-1&&b[j]==-1)add(dp[i+1][j][k+1][1][1],now);
            }
            if (j<=n){
              add(dp[i][j+1][k][0][e2],now);
              if (!e2&&a[i]==-1&&b[j+1]==-1)add(dp[i][j+1][k+1][1][1],now);
            }
          }
  fac[0]=1;for (int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
  int ans=0;
  for (int k=0;k<=n-c;k++){
    int now=1ll*fac[n-c-k]*dp[n+1][n+1][k][0][0]%mod;
    if (k&1)ans=(ans-now+mod)%mod;else ans=(ans+now)%mod;
  }printf("%d",ans);
  return 0;
}