[DP记录]ARC118E Avoid Permutations

command_block · 2021-10-30 16:53:33 · 个人记录

题意：

对于排列 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 省去。

若我们选定的集障碍点集合含有 $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;
}