[DP记录]ARC118E Avoid Permutations

**题意** ： - 对于排列 $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}$ ```cpp #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; } ```