Early's Blog

Hello, World!

0%

「2021-03-21联考」伐木累

发表于 分类于
本文字数： 4k

题目链接

题意

对于任意一个 nn 行 mm 列、由 S 与 E 组成的矩阵，由上至下、由左至右地对于每个格子进行以下操作：

  • 如果该格子已被覆盖，直接跳过。
  • 尝试覆盖这个格子与另一个：若该格子为 S 则覆盖下面的格子，为 E 则覆盖右边的格子。如果要覆盖的格子已被覆盖或不在矩阵内，则跳过。
  • 尝试向另一个方向覆盖。如果也不行则不覆盖。

对于所有可能的 2nm2^{nm} 个矩阵，求出矩阵被覆盖的次数总和。

对于 60%60\% 的数据，m≤16m\leq16。
对于 100%100\% 的数据，n≤12,m≤30n\leq12,m\leq30。

60pts

思路

容易想到一个状压 DP，fi,j,Sf_{i,j,S} 为 DP 到 (i,j)(i,j)，下图黄色格子被覆盖情况为 SS 的方案数，gi,j,Sg_{i,j,S} 为方案被覆盖次数的总和。

pic1

转移繁而不难。

时空复杂度 O(nm⋅2m)\mathcal O(nm\cdot2^m)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
using namespace std;
const int N=12,M=16;
int n,m,p;
int f[N+2][M+2][1<<M],g[N+2][M+2][1<<M];
int main()
{
    freopen("famulei.in","r",stdin);
    freopen("famulei.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    f[1][1][0]=1;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            for(int S=0;S<1<<m;++S) {
                if(S&1<<j-1) {
                    f[i][j+1][S^1<<j-1]=((long long)f[i][j+1][S^1<<j-1]+f[i][j][S]*2)%p;
                    g[i][j+1][S^1<<j-1]=((long long)g[i][j+1][S^1<<j-1]+g[i][j][S]*2)%p;
                } else {
                    bool tS=i<n,tE=(j<m)&&!(S&1<<j);
                    if(!tS&&!tE) {
                        f[i][j+1][S&~(1<<j-1)]=((long long)f[i][j+1][S&~(1<<j-1)]+f[i][j][S]*2)%p;
                        g[i][j+1][S&~(1<<j-1)]=((long long)g[i][j+1][S&~(1<<j-1)]+g[i][j][S]*2)%p;
                    } else {
                        int cS=tS+(tS&&!tE),cE=tE+(tE&&!tS);
                        if(tS) {
                            f[i][j+1][S|1<<j-1]=((long long)f[i][j+1][S|1<<j-1]+f[i][j][S]*cS)%p;
                            g[i][j+1][S|1<<j-1]=(g[i][j+1][S|1<<j-1]+1ll*(g[i][j][S]+f[i][j][S])*cS)%p;
                        }
                        if(tE) {
                            f[i][j+1][S|1<<j]=((long long)f[i][j+1][S|1<<j]+f[i][j][S]*cE)%p;
                            g[i][j+1][S|1<<j]=(g[i][j+1][S|1<<j]+1ll*(g[i][j][S]+f[i][j][S])*cE)%p;
                        }
                    }
                }
            }
        }
        for(int S=0;S<1<<m;++S) {
            f[i+1][1][S]=f[i][m+1][S];
            g[i+1][1][S]=g[i][m+1][S];
        }
    }
    printf("%d\n",g[n][m+1][0]);
    return 0;
}

100pts

思路

由于 mm 达到了 3030，状压 mm 显然不行。

能否转变思路，状压 nn？

不能状压 nn 的限制在于 (i−1,j+1)(i-1,j+1) 会影响到 (i,j)(i,j)，即下一行会影响上一行，有后效性。

非常妙的思路：从右上至左下 DP。

我们对于每一条对角线都从上往下 DP，fi,j,Sf_{i,j,S} 改为记第 ii 条对角线、第 jj 个点、状态数为 SS 的方案数，gi,j,Sg_{i,j,S} 同理。

SS 记录的状态为下图黄色格子。

pic2

由于对角线长度至多为 nn，所以时空复杂度 O((n+m) n⋅2n)\mathcal O((n+m)\,n\cdot2^n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=12,M=30;
int n,m,p;
int f[N+M+1][N+2][1<<N+1],g[N+M+1][N+2][1<<N+1];
int main()
{
    freopen("famulei.in","r",stdin);
    freopen("famulei.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    f[2][1][0]=1;
    for(int s=2;s<=n+m;++s) {
        int il=max(1,s-m),ir=min(n,s-1);
        for(int i=il,j=s-i;i<=ir;++i,--j) {
            for(int S=0;S<1<<n+1;++S) {
                if(S&1<<i) {
                    f[s][i+1][S^1<<i]=(f[s][i+1][S^1<<i]+2ll*f[s][i][S])%p;
                    g[s][i+1][S^1<<i]=(g[s][i+1][S^1<<i]+2ll*g[s][i][S])%p;
                } else {
                    bool tS=i!=n,tE=(j!=m)&&!(S&1<<i-1);
                    if(!tS&&!tE) {
                        f[s][i+1][S&~(1<<i)]=(f[s][i+1][S&~(1<<i)]+2ll*f[s][i][S])%p;
                        g[s][i+1][S&~(1<<i)]=(g[s][i+1][S&~(1<<i)]+2ll*g[s][i][S])%p;
                    } else {
                        int cS=tS+(tS&&!tE),cE=tE+(tE&&!tS);
                        f[s][i+1][S|1<<i]=(f[s][i+1][S|1<<i]+1ll*cS*f[s][i][S])%p;
                        g[s][i+1][S|1<<i]=(g[s][i+1][S|1<<i]+1ll*cS*(g[s][i][S]+f[s][i][S]))%p;
                        f[s][i+1][S|1<<i-1]=(f[s][i+1][S|1<<i-1]+1ll*cE*f[s][i][S])%p;
                        g[s][i+1][S|1<<i-1]=(g[s][i+1][S|1<<i-1]+1ll*cE*(g[s][i][S]+f[s][i][S]))%p;
                    }
                }
            }
        }
        int til=max(1,s-m+1);
        if(s!=n+m) {
            for(int S=0;S<1<<n+1;++S) {
                f[s+1][til][S<<1]=(f[s+1][til][S<<1]+f[s][ir+1][S])%p;
                g[s+1][til][S<<1]=(g[s+1][til][S<<1]+g[s][ir+1][S])%p;
            }
        }
    }
    printf("%d\n",g[n+m][n+1][0]);
    return 0;
}