关于在矩阵中枚举点的 dp

关于在矩阵中枚举点的 dp

JOISC 2018 Day1 camp

简要题意：

在矩阵中放一个点，每个点所在的行与列至多有一个别的点，且若有点，两个点的方向要相对，而若无点，则可任意指向四个方向。

考虑 dp 。

首先是 $70$ 分的思路。令 $d{p}_{i,j,k}$ 表示到第 $i$ 行，此时还剩 $j$ 个空列，剩 $k$ 个只能放一个的列(即此列中上方已经有一个点方向向下，次格放的点只能方向向上)，称之为半列。

• $d{p}_{i,j,k}+=d{p}_{i-1,j+2,k}\times C_{j+2}^2$
• $d{p}_{i,j,k}+=d{p}_{i-1,j+1,k-1}\times (j+1)$
• $d{p}_{i,j,k}+=d{p}_{i-1,j,k+1}\times (k+1)$
• $d{p}_{i,j,k}+=d{p}_{i-1,j+1,k}\times (j+1)\times 3$

第一个方程表示选择两个空列；第二个方程表示，选择一个空列，令点的方向向下，形成一个半列；第三个方程表示选择一个半列，让这一列填满；第四个方程表示选择一个空列，放的点的方向指向左右上(若向下则会形成一个半列)。

然后是 $100$ 分的思路。

令 $d{p}_{i,j}$ 表示把 $i\times j$ 的矩阵填满，可能得方案数。转移方程：

• $d{p}_{i,j}+=d{p}_{i-1,j-1}\times 4\times j$
• $d{p}_{i,j}+=d{p}_{i-2,j-1}\times (i-1)\times j$
• $d{p}_{i,j}+=d{p}_{i-1,j-2}\times C_j^2$

第一个方程表示将矩阵拓展一行一列，由于新的一行一列是空列，有四个方向，我们只考虑向下拓展行，而可以在任意位置拓展列，在行列交点处放一个点，由于行列上没有其他点，故有四个方向；第二个方程表示拓展两行一列，每行放置一个，让两个格子的方向相对，使那个列填满，其中一行必然在最底下，而另一行则可以选择位置插入；第三个方程表示拓展一行两列，让两个格子在同一行，让这一行填满，任意插入两列。最后计算时由于行列之间可以任意插入空的行列，故 $ans=\sum _{i=0}^n\sum _{j=0}^{m}d{p}_{n-i,j-m}\times C_n^i\times C_m^j-1$ (减去一是为了减去一个格子都不放的情况)。

总体来说对于行列，只有两种情况：放了两个，并且相对；放了一个，可以朝四个方向。通过不断添行列巧妙避免重复，同时较为快速算出答案。

Code:

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int N=3010;
long long dp[N][N],ans;
long long jc[N+10],rejc[N+10];
int n,m;
long long ksm(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
long long c(int x,int y){
    return jc[x]*rejc[y]%mod*rejc[x-y]%mod;
}
void update(long long&x,long long y){
    x+=y;
    if(x>=mod) x-=mod;
}
int main(){
    scanf("%d%d",&n,&m);
    jc[0]=1;
    for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;
    rejc[N]=ksm(jc[N],mod-2);
    for(int i=N-1;i>=0;i--) rejc[i]=rejc[i+1]*(i+1)%mod;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=dp[i-1][j-1]*j*4%mod;
            if(i>=2) update(dp[i][j],dp[i-2][j-1]*(i-1)*j%mod);
            if(j>=2) update(dp[i][j],dp[i-1][j-2]*c(j,2)%mod);
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++) update(ans,dp[n-i][m-j]*c(n,i)%mod*c(m,j)%mod);
    }
    printf("%lld",ans-1);
    return 0;
}