[ABC248F] Keep Connect Solution

更好的阅读体验戳此进入

题面

给定 $n,p$$n, p$，存在如图的 $2\times n$$2 \times n$ 的网格图，显然初始共有 $2n$$2n$ 个顶点和 $3n-2$$3n - 2$ 条边，分别求删除 $i\in [1,n-1]$$i \in [1, n - 1]$ 条边后仍使图连通的删边方案数，对 $p$$p$ 取模。

Solution

这种题 DP 很显然，考虑设状态 $dp(i,j,0/1)$$dp(i, j, 0/1)$ 表示考虑前 $i$$i$ 列，删除了 $j$$j$ 条边，第 $i$$i$ 列上下两点之间是否连边，然后对不同情况无脑进行分类讨论即可。

具体地，对于 $dp(i,j,0)$$dp(i, j, 0)$，如下图，此时 $i$$i$ 位置两个点竖直方向并未连边，则为了保证连通性，那么 $i$$i$ 到 $i+1$$i + 1$ 的水平的两个边必须连上，而 $i+1$$i + 1$ 的竖直的边（即虚线边）是否连结均合法，则有如下转移：

对于 $dp(i,j,1)$$dp(i, j, 1)$，如下图，三条边都不能直接确定，所以需要继续讨论，具体地，可以讨论 $i+1$$i + 1$ 的竖直边是否连结，简单想一下就有如下 $4$$4$ 个转移，此处不多赘述，直接看方程吧。

同时注意 $\times 2$$\times 2$ 是因为要枚举上下的两个水平边删掉其中一个。

边界可以是 $dp(1,0,1)=dp(1,1,0)=1$$dp(1, 0, 1) = dp(1, 1, 0) = 1$，对应删边数 $d$$d$ 的答案即为 $dp(n,d,1)$$dp(n, d, 1)$。

Code

xxxxxxxxxx
58
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template< typename T = int >
23
inline T read(void);
24

25
int N; int MOD;
26
int dp[3100][3100][2];
27

28
int main(){
29
    N = read(), MOD = read();
30
    dp[1][0][1] = dp[1][1][0] = 1;
31
    for(int i = 1; i <= N - 1; ++i)
32
        for(int j = 0; j <= N - 1; ++j)
33
            dp[i + 1][j + 1][0] = ((ll)dp[i + 1][j + 1][0] + dp[i][j][0]) % MOD,
34
            dp[i + 1][j][1] = ((ll)dp[i + 1][j][1] + dp[i][j][0]) % MOD,
35
            dp[i + 1][j + 1][1] = ((ll)dp[i + 1][j + 1][1] + dp[i][j][1] * 2ll) % MOD,
36
            dp[i + 1][j][1] = ((ll)dp[i + 1][j][1] + dp[i][j][1]) % MOD,
37
            dp[i + 1][j + 2][0] = ((ll)dp[i + 1][j + 2][0] + dp[i][j][1] * 2ll) % MOD,
38
            dp[i + 1][j + 1][1] = ((ll)dp[i + 1][j + 1][1] + dp[i][j][1]) % MOD;
39
    for(int i = 1; i <= N - 1; ++i)printf("%d%c", dp[N][i][1], i == N - 1 ? '\n' : ' ');
40
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
41
    return 0;
42
}
43

44
template < typename T >
45
inline T read(void){
46
    T ret(0);
47
    int flag(1);
48
    char c = getchar();
49
    while(c != '-' && !isdigit(c))c = getchar();
50
    if(c == '-')flag = -1, c = getchar();
51
    while(isdigit(c)){
52
        ret *= 10;
53
        ret += int(c - '0');
54
        c = getchar();
55
    }
56
    ret *= flag;
57
    return ret;
58
}

UPD

update-2022_11_21 初稿