关于在矩阵中枚举点的 dp

发布于:2024-11-28 ⋅ 阅读:(28) ⋅ 点赞:(0)

关于在矩阵中枚举点的 dp

JOISC 2018 Day1 camp

简要题意:

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

考虑 dp 。

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

  • d p i , j , k + = d p i − 1 , j + 2 , k × C j + 2 2 dp_{i,j,k}+=dp_{i-1,j+2,k}\times C_{j+2}^2 dpi,j,k+=dpi1,j+2,k×Cj+22
  • d p i , j , k + = d p i − 1 , j + 1 , k − 1 × ( j + 1 ) dp_{i,j,k}+=dp_{i-1,j+1,k-1}\times(j+1) dpi,j,k+=dpi1,j+1,k1×(j+1)
  • d p i , j , k + = d p i − 1 , j , k + 1 × ( k + 1 ) dp_{i,j,k}+=dp_{i-1,j,k+1}\times(k+1) dpi,j,k+=dpi1,j,k+1×(k+1)
  • d p i , j , k + = d p i − 1 , j + 1 , k × ( j + 1 ) × 3 dp_{i,j,k}+=dp_{i-1,j+1,k}\times(j+1)\times3 dpi,j,k+=dpi1,j+1,k×(j+1)×3

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

然后是 100 100 100 分的思路。

d p i , j dp_{i,j} dpi,j 表示把 i × j i\times j i×j 的矩阵填满,可能得方案数。转移方程:

  • d p i , j + = d p i − 1 , j − 1 × 4 × j dp_{i,j}+=dp_{i-1,j-1}\times4\times j dpi,j+=dpi1,j1×4×j
  • d p i , j + = d p i − 2 , j − 1 × ( i − 1 ) × j dp_{i,j}+=dp_{i-2,j-1}\times(i-1)\times j dpi,j+=dpi2,j1×(i1)×j
  • d p i , j + = d p i − 1 , j − 2 × C j 2 dp_{i,j}+=dp_{i-1,j-2}\times C_{j}^{2} dpi,j+=dpi1,j2×Cj2

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

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

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;
}