AGC046B-Extension题解

发表于 分类于

题目传送门

题意：有一个 A×BA\times B 的矩阵，所有格子全为白色。每次可以选择往右添加一列或网上添加一行白格子，并选择添加的其中一个格子染成黑色，问变成 C×DC\times D 的矩阵时图案的方案数。

做法一

By betrue12

B - 扩展

首先考虑以下 DP

dp[i][j]=dp[i][j]= 通过本问题的操作，可以操作到有垂直 ii 行和水平 jj 列的板数。

看起来，这个 DP 中的 "在上面加一排，把其中一排涂成黑色 "的转移和 "在右边加一列，把其中一列涂成黑色 "的转移已经足够了，但重要的是最后的板数，所以必须注意，即使中间的操作列不一样，也不要把同一个东西重复成板。

尽管操作列不同，但有结果相同的操作，特别是

因此，在一个 i×ji\times j 的板上

  • 右上角不是黑色的
  • 最上面一行和最右边一列都有一个黑色方块
  • 一个或多个行和列已经从初始状态添加了
    满足 (i−1)×(j−1)(i-1)\times (j-1) 的所有条件，可以通过两种不同的方式从 (i−1)×(j−1)(i-1)\times (j-1) 板中得到。

更一般地说，如果有 xx 行和 yy 列，从上面看正好有一个黑色方块，从右边看有 yy 个，而且在它们相交的地方没有黑色方块，那么有 (x+yx)\binom{x+y}{x} 种方法可以从 (i−x)×(j−y)(i-x)\times(j-y) 棋盘上依次增加行和列。

从以下事实可以看出，只有这样的重复模式，对于任何其他棋盘来说，最多只有一个可以考虑反向操作（去除最上面的一行或最右边的一列，正好有一个黑色的方块）的操作，而不会把下一个操作也卡住。

因此，DP 的规则是，只有一个具体的这样的操作序列可以被采纳为一个过渡。 例如，假设我们只采用 “将所有行添加到顶部，然后将所有列添加到右侧”。 在这种情况下，当过渡到右侧添加一列时

  • 除了该列的顶部边缘（右上角）外，其他地方都要涂抹。
  • 过渡前最上面一行的一个黑色方块
  • 自初始状态以来，已经添加了一个或多个行

如果满足上述所有条件，那么这个过渡应该被取消，因为它是一个被计入不同操作行的棋盘。

为了能够确定这一点，应将DP表扩展到

dp[i][j][a][b]=dp[i][j][a][b]= 本问题中可操作的木板数量，直到有 ii 个垂直行和 jj 个水平列，使得最上面一行有 aa 个黑方块，最右边一列有 bb 个黑方块为止。

(实际上，A或B都可以）。 由于这里使用的决定是 “是否正好有一个黑方块”，因此将 “0”、"1 "和 "2以上 "区分为 aa 和 bb 即可。

通过将过渡划分为总共四个过渡–"在顶部添加一行，并将其右侧/非右侧边缘涂成黑色 "和 “在右侧添加一列，并将其顶部/非顶部边缘涂成黑色”–可以计算出过渡的 aa 和 bb，并判断是否应该取消这些过渡。 每个非右侧/非顶部过渡必须乘以候选方格的数量作为系数。

答案是 a,ba,b 的 dp[C][D][a][b]dp[C][D][a][b] 之和。

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
int main(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    static int64_t dp[3002][3002][3][3];
    dp[A][B][0][0] = 1;
    for(int i=A; i<=C; i++) for(int j=B; j<=D; j++) for(int a=0; a<3; a++) for(int b=0; b<3; b++){
        // 上、隅以外
        {
            add(dp[i+1][j][1][b], dp[i][j][a][b] * (j-1));
        }
        // 上、隅
        {
            add(dp[i+1][j][1][min(2, 1+b)], dp[i][j][a][b]);
        }
        // 右、隅以外
        {
            if(a != 1 || i==A) add(dp[i][j+1][a][1], dp[i][j][a][b] * (i-1));
        }
        // 右、隅
        {
            add(dp[i][j+1][min(2, 1+a)][1], dp[i][j][a][b]);
        }
    }

    int64_t ans = 0;
    for(int a=0; a<3; a++) for(int b=0; b<3; b++) add(ans, dp[C][D][a][b]);
    cout << ans << endl;
    return 0;
}

做法二

同样考虑 DP：f[i][j]f[i][j] 表示填到 ii 行 jj 列的图案方案数。很容易想到基本的转移式框架：f[i][j]=f[i−1][j]×j+f[i][j−1]×if[i][j]=f[i-1][j]\times j+f[i][j-1]\times i，分别表示最后一步为添加一行和添加一列。

这个题的难点主要在如何去重。首先发现一个性质：如果算出来的 f[i][j]f[i][j] 是去重的，所有方案互不相同，那么往后无论怎么添加，不同的仍然一定互不相同。所以只需要在每一步转移的时候去重，而不需要考虑以前的重复。

每一步转移的去重为，在 f[i−1][j]×j+f[i][j−1]×if[i-1][j]\times j+f[i][j-1]\times i 的两项的方案中，有多少种是重复的，减去即可。也就相当于问，有多少种 i×ji\times j 的图案，既能从 (i−1)×j(i-1)\times j 添加一行转移来，也能从 i×(j−1)i\times(j-1) 添加一列转移来。

思考一下可以发现，如果这 i×ji\times j 的图案右上角格子为黑色，则一定只能从行列之一转移。假设最后一步添加了一行，那么右上角一定归属于最上面一行，所以最上面一行一定没有其他黑格子，于是显然最后一步只能为一行而不能为列。

反之，如果右上角的格子为白色，则一定既能从行转移也能从列转移吗？并不是。如果最右边的列有超过一个黑格子，最后一步一定不能添加右边的列。最上面的行同理。

所以，既能从行转移也能从列转移的充要条件为：右上角为白格子，最上面一行和最右边一列都只有一个黑格子。这样的方案数有多少呢？显然为 f[i−1][j−1]×(i−1)×(j−1)f[i-1][j-1]\times (i-1)\times(j-1)。

于是最终的转移方程非常简单：f[i][j]=f[i−1][j]×j+f[i][j−1]×i−f[i−1][j−1]×(i−1)×(j−1)f[i][j]=f[i-1][j]\times j+f[i][j-1]\times i-f[i-1][j-1]\times(i-1)\times(j-1)。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int f[3010][3010];
signed main() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    f[a][b]=1;
    for(int i=a;i<=c;i++)
        for(int j=b;j<=d;j++) {
            if(i==a&&j==b) continue;
            f[i][j]=(1ll*f[i-1][j]*j%mod+1ll*f[i][j-1]*i%mod-1ll*f[i-1][j-1]*(i-1)%mod*(j-1)%mod+mod)%mod;
        }
    cout<<f[c][d]<<endl;
    return 0;
}

做法三

设 f[i][j][0/1]f[i][j][0/1] 表示 ii 行 jj 列，最后一次操作了行还是列的图案方案数。DP 框架相同，在去重时，ii 行 jj 列最后一次选行和选列会有重复部分，将列的重复部分删掉只留下不重复的即可。思考可以发现，列和行的重复部分一定是先走一次行再走一次列和先走列再走行的重复，所以禁止先走行再走列即可。但是这没有考虑到最后一步的列走在右上角，此时没有重复，不能禁止，所以加上这一种选择即可。

By ecnerwala

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
int main() {
    using namespace std;
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    using num = modnum<998244353>;

    int A, B, C, D; cin >> A >> B >> C >> D;
    assert(A <= C && B <= D);
    tensor<array<num, 2>, 2> dp({C+1, D+1});
    dp[{A,B}][1] ++;
    for (int i = A; i <= C; i++) {
        for (int j = B; j <= D; j++) {
            if (i < C) {
                dp[{i+1, j}][0] += dp[{i,j}][0] * j;
                dp[{i+1, j}][0] += dp[{i,j}][1] * j;
            }
            if (j < D) {
                dp[{i, j+1}][1] += dp[{i,j}][0];
                dp[{i, j+1}][1] += dp[{i,j}][1] * i;
            }
        }
    }
    cout << dp[{C,D}][0] + dp[{C,D}][1] << '\n';

    return 0;
}