JLOI2015 骗我呢

Link

题意

给出$n,m$,求满足下面条件的$n\times m$的矩阵个数。

$$
\begin{cases}
x_{ij} \in [0, m]\\
x_{ij}< x_{i,j+1}\\
x_{ij}< x_{i-1,j+1}\\
\end{cases}
$$
数据范围$n,m \leq 1e6$

暴力DP

因为每个数只能在$0\sim m$中选,也就是说每一列有一个数不能选。

设$dp[i][j]$表示前$i$行中,第$i$行不选$j$的方案数。

可以得到转移:
$$
dp[i][j]=\sum_{k=0}^{j+1}dp[i-1][k]
$$
前缀和优化一下
$$
dp[i][0]=dp[i-1][0]\\
dp[i][m]=dp[i-1][m-1]\\
\text{otherwise}~~~
dp[i][j]=dp[i][j-1]+dp[i][j+1]
$$

考虑转化

我们把转移变成边,得到下图。

由于可以向左下和右转移,有一点麻烦,我们加入虚拟结点,把每一层平移,把他变成可以向下和向右转移。

得到了一个$n \times (n+m+1)$的矩阵。

因为最优的答案是最后一层的和,可以新加一层,$(n+1,n+m+1)$点就是要求的总答案。

为了更加直观地转化,可以把他旋转180度以后翻转,对应到坐标系中。

答案就是从$(1,1)$到$(n+m+1,n)$的路径数,但是这个过程中不能接触到直线$A,B$

$A:y=x+1,B:y=x-(m+2)$

计数

如果不考虑这两个直线,从原点到$(x,y)$的方案数为$\binom {x+y}x$。

可以理解为从$x+y$步中选择$x$步向上,其他向右的方案。

但是这两条直线看起来还是不太好处理,不如采用一波容斥的思想。

答案等于:总答案减去就经过$A,B$的答案。但是这还是不太好算。

把一个方案按照$ABABABA….$表示穿过了$A$,$B$这两条直线。

如果把$(x,y)$沿着直线$A$对称得到$(x’,y’)$,从原点到$(x’,y’)$的方案沿着$A$对称回去一定是一个不合法的方案。

而且这个方案一定是以$A$结尾或者是以$AB$结尾。

然后把$(x’,y’)$沿着$B$对称,得到$(x”,y”)$,把原点到这个点的方案加回来,相当于加上了以$BA$和$BAB$结尾的方案数。

减去$A,AB$结尾然后加上$BA,BAB$结尾,减去$ABA,ABAB$结尾,加上..

最后到$x,y$坐标非法$(x< 0$或$y< 0)$就结束。

这样下来最终我们减去的就是所有以$A$开头的方案。

同样的方法,先按照$B$对称,然后减去所有以B开头的方案。

最后的就是答案。不得不说这题太妙了。

代码

代码其实很短,而且很好实现。

Leave a Reply

Your email address will not be published. Required fields are marked *